Submission #837966

#	Time	Username	Problem	Language	Result	Execution time	Memory
837966		1075508020060209tc	Joker (BOI20_joker)	C++14	25 / 100	361 ms	11480 KiB

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
• Subtask 2: 0 / 8
• Subtask 3: 25 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29