Submission #3221942
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
int n,m,Q;
int fa[N],size[N],id[N],cur=0;
struct Edge{
int x,y;
}e[N];
struct Query{
int x,y,z,ans;
}q[N];
void clear_fa(){
for (int i=1;i<=n;i++)
fa[i]=i,size[i]=1;
}
int getf(int x){
return fa[x]==x?x:fa[x]=getf(fa[x]);
}
void Merge(int x,int y){
x=getf(x),y=getf(y);
if (x!=y)
size[fa[y]=x]+=size[y];
}
struct Node{
int L,R,Q;
int *id;
Node(){}
Node(int a,int b,int *d,int c){
L=a,R=b,Q=c,id=d;
}
}s[N<<5];
int head,tail;
int tL[N],cL;
int tR[N],cR;
void Insert(int L,int R,int *id,int Q){
s[++tail]=Node(L,R,id,Q);
}
int calc(int x,int y){
x=getf(x),y=getf(y);
return x==y?size[x]:(size[x]+size[y]);
}
void solve(int L,int R,int *id,int Q){
if (L>R||Q==0)
return;
int mid=(L+R)>>1;
if (cur>mid)
clear_fa(),cur=0;
while (cur<mid)
cur++,Merge(e[cur].x,e[cur].y);
cL=cR=0;
for (int i=1;i<=Q;i++){
int ID=id[i],res=calc(q[ID].x,q[ID].y);
if (res>=q[ID].z)
tL[++cL]=ID,q[ID].ans=min(q[ID].ans,mid);
else
tR[++cR]=ID;
}
for (int i=1;i<=cL;i++)
id[i]=tL[i];
for (int i=1;i<=cR;i++)
id[cL+i]=tR[i];
Insert(L,mid-1,id,cL);
Insert(mid+1,R,id+cL,cR);
}
void BFS(int L,int R,int *id,int Q){
head=tail=0;
clear_fa();
Insert(L,R,id,Q);
while (head<tail)
head++,solve(s[head].L,s[head].R,s[head].id,s[head].Q);
}
int main(){
n=read(),m=read();
for (int i=1;i<=m;i++)
e[i].x=read(),e[i].y=read();
Q=read();
for (int i=1;i<=Q;i++)
q[i].x=read(),q[i].y=read(),q[i].z=read(),id[i]=i,q[i].ans=m;
BFS(1,m,id,Q);
for (int i=1;i<=Q;i++)
printf("%d\n",q[i].ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Stamp Rally |
User |
zhouzhendong |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
1837 Byte |
Status |
AC |
Exec Time |
166 ms |
Memory |
10112 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt |
All |
0_00.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
2304 KB |
1_00.txt |
AC |
67 ms |
10112 KB |
1_01.txt |
AC |
87 ms |
10112 KB |
1_02.txt |
AC |
67 ms |
10112 KB |
1_03.txt |
AC |
88 ms |
10112 KB |
1_04.txt |
AC |
71 ms |
10112 KB |
1_05.txt |
AC |
89 ms |
10112 KB |
1_06.txt |
AC |
70 ms |
10112 KB |
1_07.txt |
AC |
90 ms |
10112 KB |
1_08.txt |
AC |
71 ms |
10112 KB |
1_09.txt |
AC |
91 ms |
10112 KB |
1_10.txt |
AC |
76 ms |
10112 KB |
1_11.txt |
AC |
95 ms |
10112 KB |
1_12.txt |
AC |
85 ms |
10112 KB |
1_13.txt |
AC |
100 ms |
10112 KB |
1_14.txt |
AC |
72 ms |
8192 KB |
1_15.txt |
AC |
82 ms |
8192 KB |
1_16.txt |
AC |
141 ms |
5248 KB |
1_17.txt |
AC |
161 ms |
5888 KB |
1_18.txt |
AC |
158 ms |
5888 KB |
1_19.txt |
AC |
143 ms |
5248 KB |
1_20.txt |
AC |
152 ms |
5632 KB |
1_21.txt |
AC |
149 ms |
5376 KB |
1_22.txt |
AC |
157 ms |
5760 KB |
1_23.txt |
AC |
160 ms |
6016 KB |
1_24.txt |
AC |
166 ms |
8192 KB |
1_25.txt |
AC |
156 ms |
5632 KB |
1_26.txt |
AC |
147 ms |
5504 KB |
1_27.txt |
AC |
155 ms |
5632 KB |
1_28.txt |
AC |
150 ms |
5504 KB |
1_29.txt |
AC |
164 ms |
8192 KB |
1_30.txt |
AC |
157 ms |
5888 KB |
1_31.txt |
AC |
149 ms |
5504 KB |