Submission #1039439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039439		MarwenElarbi	Joker (BOI20_joker)	C++17	100 / 100	720 ms	34488 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define se second
#define fi first
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const int nax = 2e5 + 5;
vector<int> adj[nax];
vector<pair<int,int>> edges(nax);
int opt[nax];
struct DSU{
    vector<pair<int,int>> parent;
    vector<vector<int>> hist;
    vector<int> rank;
    bool bip=true;
    void init(int n){
        parent.resize(n);
        rank.assign(n,0);
        for (int i = 0; i < n; ++i)
        {
            parent[i]={i,0};
        }
        return;
    }
    bool is_bip(){
        return bip;
    }
    pair<int,int> find(int x){
        if(x!=parent[x].fi){
            int len=parent[x].se;
            pair<int,int> v=find(parent[x].fi);
            v.se=(v.se+len)%2;
            return v;
        }
        return parent[x];
    }
    void join(int x,int y){
        if(x==y)
            return;
        pair<int,int> xx=find(x);
        pair<int,int> yy=find(y);
        if(xx.fi==yy.fi){
            hist.pb({-1,bip});
            if(xx.se==yy.se){
                bip=0;
            }
            return;
        }
        if(rank[xx.fi]<rank[yy.fi]) swap(xx,yy);
        hist.pb({yy.fi,parent[yy.fi].fi,parent[yy.fi].se,xx.fi,(rank[xx.fi]==rank[yy.fi])});
        parent[yy.fi].fi=xx.fi;
        parent[yy.fi].se=(yy.se+xx.se+1)%2;
        rank[xx.fi]+=(rank[xx.fi]==rank[yy.fi]);
    }
    void roll_back(){
        auto last=hist.back();
        hist.pop_back();
        if(last[0]==-1){
            bip=last.back();
        }else{
            parent[last[0]]={last[1],last[2]};
            rank[last[3]]-=last[4];
        }
    }
    void roll_back(int x){
        while(x--){
            roll_back();
        }
    }
}dsu;
int n,m,q;
void daq(int l,int r,int optl,int optr){
    if(l>r) return;
    int mid=(r+l)/2;
    int cnt=0;
    for (int i = l; i < mid; ++i)
    {
        cnt++;
        dsu.join(edges[i].fi,edges[i].se);
    }
    int optimum=optr;
    for (int i = optr; i >= max(mid,optl) ; --i)
    {
        if(!dsu.is_bip()){
            break;
        }
        optimum=i;
        if(i<m){
            cnt++;
            dsu.join(edges[i].fi,edges[i].se);
        }
    }
    opt[mid]=optimum;
    dsu.roll_back(cnt);
    cnt=0;
    for (int i = optimum; i <= optr; ++i)
    {
        if(i==m) continue;
        cnt++;
        dsu.join(edges[i].fi,edges[i].se);
    }
    daq(l,mid-1,optl,optimum);
    dsu.roll_back(cnt);
    cnt=0;
    for (int i = l; i <= mid; ++i)
    {
        cnt++;
        dsu.join(edges[i].fi,edges[i].se);
    }
    daq(mid+1,r,optimum,optr);
    dsu.roll_back(cnt);
    cnt=0;
}
int main(){
    cin>>n>>m>>q;
    dsu.init(n);
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        edges[i]={x,y};
        adj[x].pb(y);
        adj[y].pb(x);
    }
    daq(0,m-1,0,m);
    for (int i = 0; i < q; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        cout << (opt[x] > y ? "YES" : "NO")<<endl;
    }
}

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