Submission #1031244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031244		kl0989e	Joker (BOI20_joker)	C++17	100 / 100	492 ms	21900 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define all(x) (x).begin(),(x).end()

const int maxn=2e5+10;
vector<pi> edge(maxn);
vi head(maxn);
vi col(maxn,1);
vi depth(maxn,1);
vector<vi> changes;
bool is_bipartite=1;

pi get(int a) {
    if (a==head[a]) {
        return {a,col[a]};
    }
    else {
        pi temp=get(head[a]);
        temp.se^=col[a];
        return temp;
    }
}

void unite(int a, int b) {
    int cola,colb;
    tie(a,cola)=get(a);
    tie(b,colb)=get(b);
    if (a==b) {
        if (cola==colb) {
            is_bipartite=0;
        }
        return;
    }
    if (depth[a]<depth[b]) {
        swap(a,b);
    }
    changes.pb({b,head[b],col[b],a,int(depth[a]==depth[b])});
    head[b]=a;
    col[b]=cola^colb^1;
    depth[a]+=int(depth[a]==depth[b]);
}

void rollback(int k) {
    while (changes.size()>k) {
        vi t=changes.back();
        changes.pop_back();
        head[t[0]]=t[1];
        col[t[0]]=t[2];
        depth[t[3]]-=t[4];
    }
}

int n,m,q;
vi lim(maxn);// max r where graph is not bipartite;

void dfs(int l_added=0, int r_added=m-1, int tl=0, int tr=m-1) {
    bool temp_is_bip=is_bipartite;
    int temp_sze=changes.size();
    int tm=tl+(tr-tl)/2;
    int l=l_added,r=r_added;
    while (l<tm) {
        unite(edge[l].fi,edge[l].se);
        l++;
    }
    while (is_bipartite && r>=tm) {
        unite(edge[r].fi,edge[r].se);
        r--;
    }
    lim[tm]=r;
    rollback(temp_sze);
    is_bipartite=temp_is_bip;
    if (tl==tr) {
        return;
    }
    int tempr=r_added;
    while (r_added>r) {
        unite(edge[r_added].fi,edge[r_added].se);
        r_added--;
    }
    if (tl!=tm) {
        dfs(l_added,r_added,tl,tm-1);
    }
    is_bipartite=temp_is_bip;
    rollback(temp_sze);
    while (l_added<=tm) {
        unite(edge[l_added].fi,edge[l_added].se);
        l_added++;
    }
    dfs(l_added,tempr,tm+1,tr);
    is_bipartite=temp_is_bip;
    rollback(temp_sze);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    iota(all(head),0);
    for (int i=0; i<m; i++) {
        cin >> edge[i].fi >> edge[i].se;
        edge[i].fi--;
        edge[i].se--;
    }
    dfs();
    int l,r;
    for (int i=0; i<q; i++) {
        cin >> l >> r;
        cout << (r-1<=lim[l-1]?"YES\n":"NO\n");
    }
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void rollback(int)':
Joker.cpp:51:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     while (changes.size()>k) {
      |            ~~~~~~~~~~~~~~^~

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