Submission #1212089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212089		Malix	Joker (BOI20_joker)	C++20	49 / 100	2092 ms	10260 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,m,q;
pii a;
vector<ti> b;
vi p,s,t;
vector<pi> c,d,e;

pi parent(int x){
    if(p[x]==x)return {x,0};
    pi X=parent(p[x]);
    c.PB({x,p[x]});
    e.PB({x,t[x]});
    p[x]=X.F;
    t[x]^=X.S;
    return {p[x],t[x]};
}

bool merge(pi ed){
    int x=ed.F,y=ed.S;
    int u=x,v=y;
    pi X=parent(x),Y=parent(y);
    if(X.F==Y.F)return t[x]==t[y];
    x=X.F;y=Y.F;
    if(s[x]<s[y])swap(x,y);
    c.PB({y,p[y]});
    d.PB({x,s[x]});
    e.PB({y,t[y]});
    s[x]+=s[y];
    p[y]=x;
    t[y]=t[u]^t[v]^1;
    return 0;
}

int main() {   
ios::sync_with_stdio(0);
cin.tie(0);
    cin>>n>>m>>q;
    a.resize(m);b.resize(q);
    REP(i,0,m){
        int x,y;cin>>x>>y;
        x--;y--;
        a[i]={x,y};
    }
    REP(i,0,q){
        int x,y;cin>>x>>y;
        x--;y--;
        b[i]={x,y,i};
    }
    sort(b.begin(),b.end());
    int k=sqrt(m),val=0,pr=-1;
    vector<bool> ans(q,0);
    int pos=0;
    while(pos<q){
        p.clear();s.clear();t.clear();
        c.clear();d.clear();e.clear();
        p.resize(n);s.resize(n,1);t.resize(n,0);
        REP(i,0,n)p[i]=i;
        val=min(val+k,m-1);
        vector<ti> arr;
        while(pos<q&&get<0>(b[pos])<=val){
            arr.PB({get<1>(b[pos]),get<0>(b[pos]),get<2>(b[pos])});
            pos++;
        }
        sort(arr.begin(),arr.end());
        reverse(arr.begin(),arr.end());
        bool f=0;
        REP(i,0,pr+1)f|=merge(a[i]);
        c.clear();d.clear();e.clear();
        int ps=m-1;
        for(auto [y,x,z]:arr){
            REP(i,y+1,ps+1)f|=merge(a[i]);
            ps=y;
            c.clear();d.clear();e.clear();
            REP(i,pr+1,x)ans[z]=ans[z]|merge(a[i]);
            reverse(c.begin(),c.end());
            reverse(d.begin(),d.end());
            reverse(e.begin(),e.end());
            for(auto [u,v]:c)p[u]=v;
            for(auto [u,v]:d)s[u]=v;
            for(auto [u,v]:e)t[u]=v;
            c.clear();d.clear();e.clear();
            ans[z]=ans[z]|f;

        }
        pr=val;
    }
    REP(i,0,q)cout<<(ans[i]?"YES\n":"NO\n");
}

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