Submission #2122243
Source Code Expand
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; vector<int> v1; vector<int> v2; struct ha { int from; int to; }e[100005]; struct haa { int L; int R; vector<int> set; }q[105]; int L[100005],R[100005],need[100005]; int f[100005],rank[100005]; int ans[100005]; int cnt; int n,m,Q; inline int find(int k) { return f[k]==k?k:f[k]=find(f[k]); } inline void join(int x,int y) { x=find(x); y=find(y); if(x==y) return; f[x]=y; rank[y]+=rank[x]; //rank[x]=0; } inline int co(int u,int v) { u=find(u); v=find(v); int tot=rank[u]; if(u==v) tot=rank[u]; else tot=rank[u]+rank[v]; return tot; } int main() { scanf("%d%d",&n,&m); register int a,b,c,d; for(a=1;a<=n;a++) f[a]=a,rank[a]=1; for(a=1;a<=m;a++) { scanf("%d%d",&b,&c); e[a].from=b; e[a].to=c; } scanf("%d",&Q); q[1].L=0; q[1].R=m; for(a=1;a<=Q;a++) { scanf("%d%d%d",&L[a],&R[a],&need[a]); q[1].set.push_back(a); } int head=1,tail=2; int cur=0; while(head<tail) { haa tmp=q[head++]; int l=tmp.L,r=tmp.R; if(r-l==1) { for(a=0;a<tmp.set.size();a++) ans[tmp.set[a]]=r; continue; } v1.clear(); v2.clear(); int mid=(l+r)>>1; if(cur>mid) { for(b=1;b<=n;b++) f[b]=b,rank[b]=1; cur=0; } while(cur<mid) { cur++; int u=e[cur].from; int v=e[cur].to; join(u,v); } for(a=0;a<tmp.set.size();a++) { int k=tmp.set[a]; int x=L[k]; int y=R[k]; if(need[k]>co(x,y)) v2.push_back(k); else v1.push_back(k); } if(v1.size()) { q[tail].L=l; q[tail].R=mid; q[tail].set.clear(); q[tail].set=v1; tail++; } if(v2.size()) { q[tail].L=mid; q[tail].R=r; q[tail].set.clear(); q[tail].set=v2; tail++; } } for(a=1;a<=Q;a++) printf("%d\n",ans[a]); return 0; } /* 5 6 2 3 4 5 1 2 1 3 1 4 1 5 6 2 4 3 2 4 4 2 4 5 1 3 3 1 3 4 1 3 5 */
Submission Info
Submission Time | |
---|---|
Task | D - Stamp Rally |
User | longgod |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2033 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void join(int, int)’: ./Main.cpp:34:2: error: reference to ‘rank’ is ambiguous rank[y]+=rank[x]; ^ ./Main.cpp:20:15: note: candidates are: int rank [100005] int f[100005],rank[100005]; ^ In file included from /usr/include/c++/5/bits/move.h:57:0, from /usr/include/c++/5/bits/stl_pair.h:59, from /usr/include/c++/5/bits/stl_algobase.h:64, from /usr/include/c++/5/bits/char_traits.h:39, from /usr/include/c++/5/ios:40, from /usr/include/c++/5/ostream:38, from /usr/include/c++/5/iostream:39, from ./Main.cpp:1: /usr/include/c++/5/type_traits:1415:12: note: template<class> struct std::rank struct rank ^ ./Main.cpp:34:11: error: reference to ‘rank’ is ambiguous rank[y]+=rank[x]; ^ ./Main.cpp:20:15: note: candidates are: int rank [100005] int f[100005],rank[100005]; ^ In file included from /usr...