Submit Info #31327

Problem Lang User Status Time Memory
Unionfind cpp 37zigen AC 202 ms 22.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.62 MiB
random_00 AC 163 ms 15.36 MiB
random_01 AC 163 ms 17.80 MiB
random_02 AC 113 ms 7.02 MiB
random_03 AC 44 ms 19.17 MiB
random_04 AC 80 ms 2.50 MiB
random_05 AC 132 ms 7.05 MiB
random_06 AC 132 ms 22.30 MiB
random_07 AC 24 ms 11.30 MiB
random_08 AC 39 ms 1.34 MiB
random_09 AC 202 ms 13.28 MiB

#include <cmath> #include "iostream" #include "vector" using namespace std; struct DSU { vector<int> pr; vector<vector<int>> ch; int p; int k; DSU(int n) { pr.resize(3*n); ch.resize(3*n); p=2*n; for (int i=0;i<3*n;++i) pr[i]=i; for (int i=0;i<n;++i) pr[i]=i+n, ch[i+n].push_back(i); k=(int)(2+log2(n)/(1+log2(1+log2(n)))); } int find(int x) { return pr[x]==x?x:find(pr[x]); } bool equiv(int x,int y) { return find(x)==find(y); } int height(int x) { return ch[x].empty()?0:(1+height(ch[x].front())); } void merge(int x,int y) { x=find(x);y=find(y); if (x==y) return; if (height(x)>height(y)) swap(x,y); if (height(x)==height(y) && ch[x].size()<ch[y].size()) swap(x,y); int hx=height(x), hy=height(y); int r=x; int v=y; while (hx!=hy) { v=ch[v].front(); hy--; } if (v!=y && ch[r].size()>=k) { ch[pr[v]].push_back(r); pr[r]=pr[v]; } else if (v==y && ch[r].size()>=k) { ch[p].push_back(r); ch[p].push_back(v); pr[r]=pr[v]=p; ++p; } else { for (int c:ch[r]) { pr[c]=v; ch[v].push_back(c); } } } }; int main(int, char* argv[]) { int N, Q; cin>>N>>Q; DSU dsu(N); for (int i=0;i<Q;++i) { int t,u,v; cin>>t>>u>>v; if (t==0) { dsu.merge(u,v); } else { cout<<dsu.equiv(u,v)<<endl; } } return 0; }