# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
660114 |
2022-11-20T11:28:07 Z |
jamezzz |
Joker (BOI20_joker) |
C++17 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
typedef pair<int,int> ii;
#define maxn 200005
int n,m,M,q,u[maxn],v[maxn],far[maxn],joined[maxn];
int par[maxn],rnk[maxn],flip[maxn];
vector<pair<ii,ii>> hist;
int fp(int i){
while(par[i]!=i)i=par[i];
return i;
}
int col(int i){
int res=0;
while(par[i]!=i)res^=flip[i],i=par[i];
return res;
}
bool join(int x,int y,bool f){
x=fp(x),y=fp(y);
if(x==y)return false;
if(rnk[x]<rnk[y])swap(x,y);
hist.pb({{x,rnk[x]},{y,rnk[y]}});
par[y]=x;
if(rnk[x]==rnk[y])++rnk[x];
if(f)flip[y]=true;
return true;
}
void undo(){
//pf("undo\n");
assert(!hist.empty());
auto[x,rx]=hist.back().fi;
auto[y,ry]=hist.back().se;
hist.pop_back();
par[x]=x,par[y]=y;
rnk[x]=rx,rnk[y]=ry;
flip[x]=flip[y]=false;
}
bool tryjoin(int i){
int cu=col(u[i]),cv=col(v[i]);
int pu=fp(u[i]),pv=fp(v[i]);
//pf("tryjoin: %d, %d %d, %d %d, %d %d\n",i,u[i],v[i],cu,cv,pu,pv);
if(pu==pv&&cu==cv)return false;
joined[i]=join(u[i],v[i],cu==cv);
return true;
}
void dnc(int l,int r,int optl,int optr){
//pf("dnc: %d %d, %d %d\n",l,r,optl,optr);
if(l>r||optl>optr)return;
int m=(l+r)>>1;
for(int i=l;i<=m;++i)tryjoin(i);
for(int i=optr;i>=optl;--i){
if(!tryjoin(i)){
far[m]=i;
break;
}
}
//pf("far %d: %d\n",m,far[m]);
for(int i=m;i>=l;--i)if(joined[i])undo();
dnc(l,m-1,optl,far[m]);
for(int i=l;i<=m;++i)tryjoin(i);
for(int i=far[m]+1;i<=optr;++i)if(joined[i])undo();
dnc(m+1,r,far[m],optr);
}
int main(){
sf("%d%d%d",&n,&m,&q);
M=m;
for(int i=1;i<=m;++i){
sf("%d%d",&u[i],&v[i]);
}
for(int i=1;i<=n;++i){
par[i]=i,rnk[i]=0,flip[i]=0;
}
for(int i=1;i<=m;++i)far[i]=m+1;
int lst=-1;
for(int i=1;i<=m;++i){
if(!tryjoin(i))break;
lst=i;
}
for(int i=1;i<=lst;++i){
if(joined[i])undo();
}
if(lst!=-1)dnc(1,lst,1,m);
for(int i=0;i<q;++i){
int l,r;sf("%d%d",&l,&r);
if(r>=far[l])pf("NO\n");
else pf("YES\n");
}
}
Compilation message
Joker.cpp: In function 'int main()':
Joker.cpp:79:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | sf("%d%d%d",&n,&m,&q);
| ^
Joker.cpp:82:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | sf("%d%d",&u[i],&v[i]);
| ^
Joker.cpp:98:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | int l,r;sf("%d%d",&l,&r);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |