__43

1278

__43
16小时前
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
const int N = 1e4 + 10;
int p[N],d[N],idx;
unordered_map<int,int>  hashmap;

int find(int x)
{
if (x != p[x])
{
int t = p[x];
p[x] = find(p[x]);
d[x] += d[t];
}
return p[x];
}

int get(int x)
{
if (!hashmap.count(x))   hashmap[x] = idx++;

return hashmap[x];
}

int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
int res = m;
for (int i = 0;i < N;++i)   p[i] = i;
for (int i = 1;i <= m;++i)
{
string op;
int a,b;
scanf("%d%d",&a,&b);
cin>>op;
a = get(a - 1),b = get(b);
int pa = find(a),pb = find(b);
int t = 0;
if ("odd" == op)   t = 1;
if (pa == pb &&  ((d[a] + d[b]) % 2 + 2) % 2 != t)//( (d[a] + d[b]) % 2 + 2) % 2 != t
{
res = i - 1;
break;
}
if (pa != pb)
{
p[pa] = pb;
d[pa] = d[a] ^ d[b] ^ t;
}

}
cout<<res<<endl;
return 0;
}


__43
19小时前
#include <iostream>
using namespace std;
const int N = 3e4 + 10;
int p[N],d[N],s[N];

int find(int x)
{
if (x != p[x])
{
int t = p[x];
p[x] = find(p[x]);
d[x] += d[t];
}
return p[x];
}

int main(void)
{
int m;
scanf("%d",&m);
for (int i = 0;i < N;++i)   p[i] = i,s[i] = 1;
for (int i = 0;i < m;++i)
{
char c[2];
int a,b;
scanf("%s%d%d",c,&a,&b);
int pa = find(a),pb = find(b);
if ('M' == *c)
{
d[pa] += s[pb];
s[pb] += s[pa];
p[pa] = pb;
}
else
{
if (pa == pb)   printf("%d\n",abs(d[a] - d[b]) - 1);
else    printf("-1\n");
}
}
return 0;
}


__43
20小时前
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 2e6 + 10;
int p[N],n,t;
unordered_map<int,int>  hashmap;
struct Edge
{
int a,b,c;
}edges[N];

int find(int x)
{
if (x != p[x])  p[x] = find(p[x]);
return p[x];
}

int get(int x)
{
if (!hashmap.count(x))    hashmap[x] = n++;
return hashmap[x];
}

int main(void)
{
scanf("%d",&t);
while (t--)
{
int m;
scanf("%d",&m);
hashmap.clear();
for (int i = 0;i < N;++i)   p[i] = i;

for (int i = 0;i < m;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edges[i] = {get(a),get(b),c};
}

for (int i = 0;i < m;++i)
if (1 == edges[i].c)
{
int pa = find(get(edges[i].a)),pb = find(get(edges[i].b));
if (pa != pb)   p[pa] = pb;
}

bool b = true;
for (int i = 0;i < m;++i)
if (0 == edges[i].c)
{
int pa = find(get(edges[i].a)),pb = find(get(edges[i].b));
if (pa == pb)
{
b = false;
break;
}
}
if (b)  puts("YES");
else    puts("NO");
}
return 0;
}


__43
1天前
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 1e4 + 10;
int p[N],w[N],v[N],n,m,val,dp[N];

int find(int x)
{
if (x != p[x])  p[x] = find(p[x]);
return p[x];
}

int main(void)
{
cin>>n>>m>>val;
for (int i = 0;i <= n;++i)  p[i] = i;
for (int i = 1;i <= n;++i)   scanf("%d%d",&w[i],&v[i]);
for (int i = 0;i < m;++i)
{
int a,b;
scanf("%d%d",&a,&b);
int pa = find(a),pb = find(b);
if (pa != pb)
{
w[pb] += w[pa];
v[pb] += v[pa];
p[pa] = pb;
}
}
for (int i = 1;i <= n;++i)
{
if (i == p[i])
{
for (int j = val;j >= w[i];--j)
{
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
}
}
}

cout<<dp[val]<<endl;
return 0;
}


__43
1天前

#include <iostream>
using namespace std;
const int N = 205 * 205;
int p[N + 10],n,m;
//#define _XY(x,y)    ((x) + ((y) - 1) * n)
int _XY(int x,int y)
{
//cout<<x<<" "<<y<<endl;
//cout<<x + (y - 1) * n<<endl;
return x + y * (n - 1);
}

int find(int x)
{
//cout<<x<<endl;
if (x != p[x])    p[x] = find(p[x]);
return p[x];
}

int main(void)
{
scanf("%d%d",&n,&m);
bool b = true;
int t = 0,temp = m;
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
p[_XY(j,i)] = _XY(j,i);
while (m--)
{
int x,y;
char c[2];
scanf("%d%d%s",&x,&y,c);
int pa = find(_XY(x,y)),pb;
if ('D' == c[0])
{
//cout<<Y<<endl;
pb = find(_XY(x,y + 1));
if (pa != pb)
p[pb] = pa;
else
{
cout<<t + 1<<endl;
break;
}
}
else
{
int X = x + 1;
pb = find(_XY(x + 1,y));
if (pa != pb)
p[pb] = pa;
else
{
cout<<t + 1<<endl;
break;
}
}
++t;
}
if (t == temp)
cout<<"draw"<<endl;
return 0;
}


__43
2天前

class Solution {
public:
unordered_map<int,int>  p;
int find(int x)
{
if (x != p[x])  p[x] = find(p[x]);
return p[x];
}
int longestConsecutive(vector<int>& nums) {
if (nums.empty())   return 0;
int res = 1,n = nums.size();
unordered_map<int,int>  hashmap;
unordered_set<int>  Set;
for (int i = 0;i < n;++i) hashmap[nums[i]] = 1,p[nums[i]] = nums[i];
for (int i = 0;i < n;++i)
{
if (Set.count(nums[i])) continue;
if (nums[i] > INT_MIN && hashmap[nums[i] - 1])
{
int pb = find(nums[i] - 1),pa = find(nums[i]);
hashmap[pa] += hashmap[pb];
p[pb] = pa;
res = max(res,hashmap[pa]);
}
Set.insert(nums[i]);
}
return res;
}
};


__43
2天前
const int N = 1e5 + 10;
int p[N],r,c;
class Solution {
public:
int find(int x)
{
if (x != p[x])  p[x] = find(p[x]);
return p[x];
}
void solve(vector<vector<char>>& board) {
if (board.empty())  return;
r = board.size();
c = board[0].size();
for (int i = 0;i < r * c;++i)   p[i] = i;
for (int i = 0;i < r;++i)
{
for (int j = 0;j < c;++j)
{
if ('O' == board[i][j])
{
int pt;
if (i && 'O' == board[i - 1][j])
{
pt = find((i - 1) * c + j);
p[pt] = i * c + j;
}
if (j && 'O' == board[i][j - 1])
{
pt = find(i * c + j - 1);
p[pt] = i * c + j;
}
}
}
}
unordered_set<int>  Set;
for (int i = 0;i < r;++i)
{
if ('O' == board[i][0])
{
int p = find(i * c);
Set.insert(p);
}
if ('O' == board[i][c - 1])
{
int p = find(i * c + c - 1);
Set.insert(p);
}
}
for (int i = 0;i < c;++i)
{
if ('O' == board[0][i])
{
int p = find(i);
Set.insert(p);
}
if ('O' == board[r - 1][i])
{
int p = find((r - 1) * c + i);
Set.insert(p);
}
}

for (int i = 1;i < r - 1;++i)
{
for (int j = 1;j < c - 1;++j)
{
int p = find(i * c + j);
if ('O' == board[i][j] && Set.find(p) == Set.end())
{
board[i][j] = 'X';
}
}
}

}
};


__43
2天前
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int r = grid.size(), c = grid[0].size();
p.resize(r * c);
for (int i = 0; i < p.size(); ++i)    p[i] = i;
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
if ('1' == grid[i][j])
{
int pt;
if (j && '1' == grid[i][j - 1])
{
pt = find(i * c + j - 1);
p[pt] = find(i * c + j);
}
if (i && '1' == grid[i - 1][j])
{
pt = find((i - 1) * c + j);
p[pt] = find(i * c + j);
}
}
}
}
unordered_set<int>  Set;
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
if ('1' == grid[i][j])
{
int pt = find(i * c + j);
Set.insert(pt);
}
}
}
return Set.size();
}
vector<int> p;
int find(int x)
{
if (x != p[x])  p[x] = find(p[x]);
return p[x];
}
};


__43
3天前
class Solution {
public:
unordered_map<string, string> p;
unordered_map<string, double> w;
string find(string& x)
{
auto it = p.find(x);
if (it == p.end())
{
p[x] = x;
w[x] = 1.0;
return x;
}
if (it->second != x)
{
string t = p[x];
p[x] = find(p[x]);
w[x] *= w[t];
}
return p[x];
}
vector<double> calcEquation(vector<vector<string>>& e, vector<double>& v, vector<vector<string>>& q) {
vector<double>  r;
int count = 0;
for (auto i : e)
{
string pa = find(i[0]), pb = find(i[1]);
p[pa] = i[1];
w[pa] = v[count] / w[i[0]];
count++;
}
for (auto i : q)
{
if (p.end() == p.find(i[0]) || p.end() == p.find(i[1]))
{
r.push_back(-1.0);
continue;
}
string pa = find(i[0]), pb = find(i[1]);
if (pa != pb)   r.push_back(-1.0);
else    r.push_back(w[i[0]] / w[i[1]]);
}
return r;
}
};


__43
3天前
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int tre[N],n,a[N],r[N];

int lowbit(int x)
{
return x & -x;
}

{
for (int i = x;i <= n;i += lowbit(i))   tre[i] += c;
}

int sum(int x)
{
int ans = 0;
for (int i = x;i;i -= lowbit(i))    ans += tre[i];
return ans;
}

int main(void)
{
scanf("%d",&n);
for (int i = 2;i <= n;++i)
{
scanf("%d",&a[i]);
}
for (int i = 1;i <= n;++i)
{
tre[i] = 1;
for (int j = i - 1;j >= i - lowbit(i) + 1;j -= lowbit(j))
tre[i] += tre[j];
}
for (int i = n;i > 0;--i)
{
int l = 1,rr = n;
int k = a[i] + 1;
while (l < rr)
{
int m = (l + rr) >> 1;
if (sum(m) >= k) rr = m;
else    l = m + 1;
}
//cout<<l+1<<endl;