Submission #1048757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048757		vjudge1	Joker (BOI20_joker)	C++14	100 / 100	190 ms	19332 KiB

Joker

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
using ll=long long;
using node=tuple<int, int, pair<int, bool>, pair<int, bool>, int, int, bool, bool>;

const int N = 2e5+13;
stack<node> roll;
int n, m, q;
int x[N], y[N];
pair<int, int> par[N];
int sz[N << 1];
int res[N];
bool bipar[N+13];
int ans;
int xx, yy;

pair<int, int> f(int v){
    if(par[v].fi==v) return {v, 0};
    pair<int, int> sus=f(par[v].fi);
    sus.se^=par[v].se;
    return sus;
}

void rollback(){
    assert(roll.size());
    node tmp=roll.top();
    roll.pop();
    int u=get<0>(tmp);
    int v=get<1>(tmp);
    par[u]=get<2>(tmp);
    par[v]=get<3>(tmp);
    sz[u]=get<4>(tmp);
    sz[v]=get<5>(tmp);
    ans-=get<6>(tmp)-bipar[u];
    ans-=get<7>(tmp)-bipar[v];
    bipar[u]=get<6>(tmp);
    bipar[v]=get<7>(tmp);
}

void uni(int u, int v){
    pair<int, bool> fu=f(u);
    pair<int, bool> fv=f(v);
    bool x=fu.se;
    bool y=fv.se;
    if(sz[fu.fi] < sz[fv.fi]){
        swap(fu, fv);
        swap(u, v);
    }
    u=fu.fi;
    v=fv.fi;
    roll.push(make_tuple(u, v, par[u], par[v], sz[u], sz[v], bipar[u], bipar[v]));
    if(u==v){
        if(x==y){
        	ans+=2*bipar[u];
            bipar[u]=0;
        }
    }
    else{
        par[v]=make_pair(u, x^y^1);
        if(bipar[u] && !bipar[v]){
        	++ans;
        }
        bipar[u]&=bipar[v];
        sz[u]+=sz[v];
    }
}

void back(int x) {
    while ((int) roll.size() > x) {
        rollback();
    }
}

void solve(int l, int r, int opl, int opr) {
    if (l > r) return;
    int mid = l+r>>1;
    int tmp = roll.size();
    for (int i = l; i <= mid - 1; i++) {
        uni(x[i], y[i]);
    }
    int cringe = roll.size();
    res[mid] = -1;
    for (int i = opr; i >= max(mid, opl); i--) {
        if (ans) {
            res[mid] = i;
            break;
        }
        uni(x[i], y[i]);
    }
    if (res[mid] == -1) res[mid] = mid - 1;
    back(cringe);
    uni(x[mid], y[mid]);
    solve(mid + 1, r, res[mid], opr);
    back(tmp);
    for (int i = opr; i > res[mid]; i--) {
        uni(x[i], y[i]);
    }
    solve(l, mid - 1, opl, res[mid]);
    back(tmp);
}

void scan(){
	for(int i=0; i<=N; i++){
		par[i]={i, 0};
		sz[i]=1;
		bipar[i]=1;
	}
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
    }
}

void sol(){
    solve(1, m, 1, m);
    while (q--) {
        cin >> xx >> yy;
        cout << (yy <= res[xx] ? "YES\n" : "NO\n");
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    sol();
}

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:79:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = l+r>>1;
      |               ~^~

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