Submission #1227783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227783		m5588ohammed	Joker (BOI20_joker)	C++20	0 / 100	305 ms	327680 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mod 1000000009
#define int long long
int parent[200001],rnk[200001],xr[200001],bib[200001],last[200001],cnt=0;
int n,m,q,num=0;
vector<tuple<int&,int,int>> history;
vector <array<int,2>> edge;
void make_set(int i){
    parent[i]=i;
    rnk[i]=bib[i]=1;
    xr[i]=0;
    return;
}
int find(int i){
    if(parent[i]==i) return i;
    int ans=find(parent[i]);
    xr[i]^=xr[parent[i]];
    return ans;
}
void merge(int s,int t){
    int a=find(s),b=find(t);
    if(a==b){
        history.emplace_back(parent[b],parent[b],0);
        history.emplace_back(bib[a],bib[a],1);
        history.emplace_back(rnk[a],rnk[a],2);
        history.emplace_back(xr[b],xr[b],3);
        //cout<<"here "<<s<<" "<<t<<" "<<xr[s]<<" "<<xr[t]<<endl;
        if(xr[s]==xr[t]){
            if(bib[a]==1) cnt++; 
            bib[a]=0;
        }
        return;
    }
    if(rnk[a]<rnk[b]){
        swap(a,b);
        swap(s,t);
    }
    // cout<<s<<" "<<t<<" "<<xr[s]<<" "<<xr[t]<<" "<<a<<" ! "<<b<<endl;
    history.emplace_back(parent[b],parent[b],0);
    history.emplace_back(bib[a],bib[a],1);
    history.emplace_back(rnk[a],rnk[a],2);
    history.emplace_back(xr[b],xr[b],3);
    if(rnk[a]==rnk[b]) rnk[a]++;
    parent[b]=a;
    xr[b]=(xr[s]^xr[t]^1);
    bib[a]=(bib[a]&bib[b]);
    return;
}
void rollback(int tm){
    //cout<<"rollback"<<endl;
    tm*=4;
    while(tm--){
        auto &[var,old_val,tp]=history.back();
        if(tp==1&&var==0&&old_val==1) cnt--;
        var=old_val;
        history.pop_back();
    }
    return;
}
void ins(int idx){
    //cout<<"edge "<<idx<<" "<<edge[idx][0]<<" "<<edge[idx][1]<<" "<<parent[(edge[idx][0])]<<" "<<parent[(edge[idx][1])]<<endl;
    merge(edge[idx][0],edge[idx][1]);
    return;
}
void solve(int l1,int l2,int r1,int r2){
    if(l1>l2||r1>r2) return;
    // cout<<"! "<<l1<<" "<<l2<<" "<<r1<<" "<<r2<<" "<<cnt<<endl;
    int lmid=(l1+l2)/2,tm;
    for(int i=l1;i<lmid;i++) ins(i);
    if(cnt!=0) last[lmid]=m+1;
    else{
        last[lmid]=0;
        for(int i=r2;i>=max(lmid,r1);i--){
            last[lmid]=i;
            ins(i);
            //cout<<lmid<<" "<<last[lmid]<<" "<<cnt<<endl;
            if(cnt!=0) break;
        }
        tm=(r2-max({lmid,r1,last[lmid]})+1);
        rollback(tm);
    }
    tm=(lmid-l1);
    rollback(tm);

    for(int i=r2;i>last[lmid];i--) ins(i);
    solve(l1,lmid-1,r1,min(r2,last[lmid]));
    tm=max(0ll,(r2-last[lmid]));
    rollback(tm);

    for(int i=l1;i<=last[lmid];i++) ins(i);
    solve(lmid+1,l2,max(last[lmid],lmid+1),r2);
    tm=(lmid-l1+1);
    rollback(tm);
    return;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>q;
    edge.push_back({0,0});
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        make_set(i);
        edge.push_back({a,b});
    }
    solve(1,m,1,m);
    //for(int i=1;i<=m;i++) cout<<last[i]<<endl;
    while(q--){
        int l,r;
        cin>>l>>r;
        if(r>=last[l]) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 22
• Subtask 5: 0 / 29
• Subtask 6: 0 / 6