Submission #551799

#	Time	Username	Problem	Language	Result	Execution time	Memory
551799		oleh1421	Joker (BOI20_joker)	C++17	71 / 100	2056 ms	22928 KiB

Joker

//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define endl '\n'
using namespace __gnu_pbds;
typedef long double ld;
//#define int ll
using namespace std;
mt19937 rnd(time(NULL));
typedef long long ll;
const int N=400100;
const int K=10000;
int a[N],b[N];
int ans[N];
int l[N/K+1];
int r[N/K+1];
int group[N];


int w[N];
int sz[N];
int dsu[N];
vector<pair<int,pair<int,int> > >CH;
pair<int,int>get(int x){
    if (x==dsu[x]) return {x,w[x]};
    auto cur=get(dsu[x]);
    cur.second^=w[x];
    return cur;
}
bool unite(int a,int b){
    auto x=get(a);
    auto y=get(b);
    if (x.first==y.first){
        return (x.second!=y.second);
    }
    if (sz[x.first]>sz[y.first]) swap(x,y);
    CH.push_back({1,{x.first,dsu[x.first]}});
    CH.push_back({2,{y.first,sz[y.first]}});
    CH.push_back({3,{x.first,w[x.first]}});
    dsu[x.first]=y.first;
    sz[y.first]+=sz[x.first];
    w[x.first]^=(x.second^y.second^1^w[y.first]);
    return true;
}
void roll_back(){
    if (!CH.empty()){
        auto cur=CH.back();
        CH.pop_back();
        if (cur.first==1) dsu[cur.second.first]=cur.second.second;
        else if (cur.first==2) sz[cur.second.first]=cur.second.second;
        else w[cur.second.first]=cur.second.second;
    }
}
int L[N],R[N];
bool used[N];
void solve(){
    int n,m,q;cin>>n>>m>>q;
    for (int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
    }
    for (int i=1;i<=q;i++){
        cin>>L[i]>>R[i];
        used[L[i]-1]=true;
    }
    int cnt=(m+K-1)/K;
    for (int i=1;i<=cnt;i++){
        l[i]=max(m-i*K+1,1);
        r[i]=m-(i-1)*K;
    }
    for (int i=1;i<=n;i++){
        dsu[i]=i;
        sz[i]=1;
        w[i]=0;
    }
    l[0]=m+1;
    r[0]=m;
    for (int i=1;i<=cnt;i++){
        bool bad=false;
        for (int j=l[i];j<=m;j++){
            if (!unite(a[j],b[j])) bad=true;
        }
        if (!bad){
            for (int j=1;j<=m;j++){
                if (!unite(a[j],b[j])) break;
                group[j]=i;
            }
        }
        while (!CH.empty()){
            roll_back();
        }
    }
    int last=cnt+1;
    bool bad=false;
    for (int i=1;i<=m;i++){
//        cout<<"G "<<i<<" "<<group[i]<<endl;
        while (last>group[i]){
            bad=false;
            last=group[i];
            while (!CH.empty()){
                roll_back();
            }
            for (int j=l[last];j<=m;j++){
                if (!unite(a[j],b[j])) bad=true;
            }
            for (int j=1;j<i;j++){
                if (!unite(a[j],b[j])) bad=true;
            }
        }
        if (!unite(a[i],b[i])) bad=true;
//        if (bad) cout<<"AAA "<<i<<endl;
        if (used[i]){
            int len=CH.size();
            if (bad) ans[i]=m+1;
            else if (last==cnt) ans[i]=0;
            else {
                for (int j=r[last+1];j>=l[last+1];j--){
    //                    if (i==3) cout<<"AAAA "<<j<<endl;

                    if (!unite(a[j],b[j])){
                        ans[i]=j;
                        break;
                    }
                }
            }
            while (CH.size()>len){
                roll_back();
            }
        }
    }
    for (int i=1;i<=n;i++){
        dsu[i]=i;
        sz[i]=1;
        w[i]=0;
    }
    CH.clear();
    ans[0]=0;
    for (int i=m;i>=1;i--){
        if (!unite(a[i],b[i])){
            ans[0]=i;
            break;
        }
    }



    for (int i=1;i<=q;i++){
        if (ans[L[i]-1]<=R[i]) cout<<"NO\n";
        else cout<<"YES\n";
    }



}

int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
    while (tt--){
        solve();
    }

    return 0;
}

/**
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7
**/

Compilation message (stderr)

Joker.cpp: In function 'void solve()':
Joker.cpp:125:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |             while (CH.size()>len){
      |                    ~~~~~~~~~^~~~

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