Submission #2708576
Source Code Expand
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;
#define Pr(f,...) //fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)
typedef long long ll;
template<typename T>
void read(T &x){
x=0;
char c;
for(c=getchar();!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())x=x*10+c-'0';
}
const int N=1e5+50;
struct Query { int x,y,z,id,ans,tg; } q[N];
bool cmpTg(Query a,Query b){return a.tg<b.tg;}
bool cmpId(Query a,Query b){return a.id<b.id;}
int n,m,a[N],b[N],p[N],qn,s[N],oa[N],ob[N],os[N],top;
int find(int x){ return p[x]==x?x:find(p[x]); }
void merge(int u,int v){
u=find(u),v=find(v);
Pr("mrege (%d,%d)\n",u,v);
if(s[u]>s[v])swap(u,v);
if(u!=v){
p[u]=v,s[v]+=s[u];
oa[++top]=u,ob[top]=v;
}
}
void solve(int l,int r,int L,int R){
Pr("solve [%d,%d] [%d,%d)\n",l,r,L,R);
//rep(i,l,r)Pr("%d %d %d\n",q[i].x,q[i].y,q[i].z);
//rep(i,1,n)Pr("s[%d]=%d,p[%d]=%d\n",i,s[i],i,p[i]);
assert(!(l<=r&&L>=R));
if(l>r){
lop(i,L,R)merge(a[i],b[i]);
top=0;
return ;
}
if(R-L==1){
rep(i,l,r)q[i].ans=L;
merge(a[L],b[L]);
top=0;
return;
}
int mid=(L+R)>>1;
Pr("mid=%d\n",mid);
lop(i,L,mid)merge(a[i],b[i]);
rep(i,l,r){
int w=find(q[i].x)==find(q[i].y)?s[find(q[i].x)]:s[find(q[i].x)]+s[find(q[i].y)];
q[i].tg=w<q[i].z;
}
sort(q+l,q+r+1,cmpTg);
int rb=l;while(rb<=r&&q[rb].tg==0)++rb;
while(top){
Pr("oa=%d,ob=%d\n",oa[top],ob[top]);
p[oa[top]]=oa[top];
s[ob[top]]-=s[oa[top]];
--top;
}
solve(l,rb-1,L,mid);
solve(rb,r,mid,R);
}
int main(int argc,char *argv[]){
freopen("dat.in","r",stdin);
read(n),read(m);
rep(i,1,m)read(a[i]),read(b[i]);
rep(i,1,n)p[i]=i,s[i]=1;
read(qn);
rep(i,1,qn){
q[i].id=i,read(q[i].x),read(q[i].y),read(q[i].z);
}
solve(1,qn,1,m+1);
sort(q+1,q+qn+1,cmpId);
rep(i,1,qn)printf("%d\n",q[i].ans);
return 0;
}
Submission Info
Submission Time
2018-06-21 10:22:59+0900
Task
E - Candy Piles
User
ax7e
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2208 Byte
Status
TLE
Exec Time
2103 ms
Memory
2304 KB
Compile Error
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:80:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("dat.in","r",stdin);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1400
Status
Set Name
Test Cases
Sample
0_00.txt, 0_01.txt, 0_02.txt
All
0_00.txt, 0_01.txt, 0_02.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, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt
Case Name
Status
Exec Time
Memory
0_00.txt
TLE
2103 ms
2304 KB
0_01.txt
TLE
2103 ms
2304 KB
0_02.txt
TLE
2103 ms
2304 KB
1_00.txt
TLE
2103 ms
2304 KB
1_01.txt
TLE
2103 ms
2304 KB
1_02.txt
TLE
2103 ms
2304 KB
1_03.txt
TLE
2103 ms
2304 KB
1_04.txt
TLE
2103 ms
2304 KB
1_05.txt
TLE
2103 ms
2304 KB
1_06.txt
TLE
2103 ms
2304 KB
1_07.txt
TLE
2103 ms
2304 KB
1_08.txt
TLE
2103 ms
2304 KB
1_09.txt
TLE
2103 ms
2304 KB
1_10.txt
TLE
2103 ms
2304 KB
1_11.txt
TLE
2103 ms
2304 KB
1_12.txt
TLE
2103 ms
2304 KB
1_13.txt
TLE
2103 ms
2304 KB
1_14.txt
TLE
2103 ms
2304 KB
1_15.txt
TLE
2103 ms
2304 KB
1_16.txt
TLE
2103 ms
2304 KB
1_17.txt
TLE
2103 ms
2304 KB
1_18.txt
TLE
2103 ms
2304 KB
1_19.txt
TLE
2103 ms
2304 KB
1_20.txt
TLE
2103 ms
2304 KB
1_21.txt
TLE
2103 ms
2304 KB
1_22.txt
TLE
2103 ms
2304 KB
1_23.txt
TLE
2103 ms
2304 KB
1_24.txt
TLE
2103 ms
2304 KB
1_25.txt
TLE
2103 ms
2304 KB
1_26.txt
TLE
2103 ms
2304 KB
1_27.txt
TLE
2103 ms
2304 KB
1_28.txt
TLE
2103 ms
2304 KB
1_29.txt
TLE
2103 ms
2304 KB
1_30.txt
TLE
2103 ms
2304 KB
1_31.txt
TLE
2103 ms
2304 KB
1_32.txt
TLE
2103 ms
2304 KB
1_33.txt
TLE
2103 ms
2304 KB
1_34.txt
TLE
2103 ms
2304 KB
1_35.txt
TLE
2103 ms
2304 KB
1_36.txt
TLE
2103 ms
2304 KB
1_37.txt
TLE
2103 ms
2304 KB
1_38.txt
TLE
2103 ms
2304 KB
1_39.txt
TLE
2103 ms
2304 KB
1_40.txt
TLE
2103 ms
2304 KB
1_41.txt
TLE
2103 ms
2304 KB
1_42.txt
TLE
2103 ms
2304 KB
1_43.txt
TLE
2103 ms
2304 KB
1_44.txt
TLE
2103 ms
2304 KB
1_45.txt
TLE
2103 ms
2304 KB
1_46.txt
TLE
2103 ms
2304 KB
1_47.txt
TLE
2103 ms
2304 KB
1_48.txt
TLE
2103 ms
2304 KB
1_49.txt
TLE
2103 ms
2304 KB
1_50.txt
TLE
2103 ms
2304 KB
1_51.txt
TLE
2103 ms
2304 KB