Submission #837966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
837966	2023-08-26T01:07:20 Z	1075508020060209tc	Joker (BOI20_joker)	C++14	25 / 100	361 ms	11480 KB

Joker

#include <bits/stdc++.h>
using namespace std;
int n;int m;int Q;
int ar[400005];
int br[400005];
int uf[200005];
int isbip;
int sz[200005];
int ufv[200005];
stack<int>stk;
stack<int>stkv;
stack<int>stkbp;
int fin(int x){
if(uf[x]==x){return x;}
return fin(uf[x]);
}
int finv(int x){
if(uf[x]==x){return 0;}
return (ufv[x]+finv(uf[x]))%2;
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){
    stk.push(0);stkbp.push(isbip);
    if(finv(a)==finv(b)){
        isbip=0;
    }
    return;
}
stkbp.push(isbip);
if(sz[pa]<sz[pb]){swap(pa,pb);swap(a,b);}
int va=finv(a);int vb=finv(b);
if(va==vb){
   // stkv.push(1);
    ufv[pb]=1;
    uf[pb]=pa;
    sz[pa]+=sz[pb];
}else{
    //stkv.push(0);
    ufv[pb]=0;
    uf[pb]=pa;
    sz[pa]+=sz[pb];
}
stk.push(pb);
}
void rollback(){
int pb=stk.top();
if(pb==0){
    stk.pop();//stkv.pop();
    isbip=stkbp.top();
    stkbp.pop();
    return;
}
isbip=stkbp.top();
stk.pop();stkbp.pop();
int pa=uf[pb];
sz[pa]-=sz[pb];
uf[pb]=pb;
ufv[pb]=0;
}




signed main(){
cin>>n>>m>>Q;
for(int i=1;i<=m;i++){
    cin>>ar[i]>>br[i];
    ar[i+m]=ar[i];
    br[i+m]=br[i];
}
for(int i=1;i<=n;i++){
    uf[i]=i;
    ufv[i]=0;
    sz[i]=1;
}
isbip=1;
int lpl=0;
for(int i=m;i>=1;i--){
    mrg(ar[i],br[i]);
    if(!isbip){
        lpl=i;break;
    }
}
for(int i=1;i<=Q;i++){
    int l;int r;
    cin>>l>>r;
    if(r<lpl){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

}

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	348 ms	10108 KB	Output is correct
4	Correct	353 ms	11480 KB	Output is correct
5	Correct	354 ms	10572 KB	Output is correct
6	Correct	344 ms	10048 KB	Output is correct
7	Correct	346 ms	10040 KB	Output is correct
8	Correct	341 ms	9028 KB	Output is correct
9	Correct	340 ms	9544 KB	Output is correct
10	Correct	338 ms	10828 KB	Output is correct
11	Correct	360 ms	9972 KB	Output is correct
12	Correct	358 ms	11108 KB	Output is correct
13	Correct	352 ms	8980 KB	Output is correct
14	Correct	354 ms	9552 KB	Output is correct
15	Correct	361 ms	10444 KB	Output is correct
16	Correct	355 ms	11296 KB	Output is correct