Submission #1199797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199797		dosts	Joker (BOI20_joker)	C++20	0 / 100	38 ms	9144 KiB

Joker

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt")
//#define int long long
#define vi vector<int>
#define pii pair<int,int> 
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
 
using namespace std;
const int N = 200001;
int dad[N],d[N];

int dep;
int bipartite = 1;
int n,m,q;
int find(int x) {
    if (x == dad[x]) {
        dep = d[x] = 0;
        return x;
    }
    dad[x] = find(dad[x]);
    dep^=d[x];
    d[x] = dep;
    return dad[x];
}
vector<pair<int,pair<int*,int>>> upds;
int timer = 0;
void unite(int x,int y) {
    ++timer;
    if (!bipartite) return;
    int a = find(x),b = find(y);
    if (a == b) {
        if (d[x] == d[y]) {
            upds.push_back({timer,{&bipartite,1}});
            bipartite = 0;
        }
        return;
    }
    dad[a] = b;
    upds.push_back({timer,{&dad[a],dad[a]}});
    d[a] = (d[x]^d[y]^1);
    upds.push_back({timer,{&d[a],d[a]}});
}

void rollback(int t = timer-1) {
    while (!upds.empty() && upds.back().ff > t) {
        *upds.back().ss.ff = upds.back().ss.ss;
        upds.pop_back();
    }
    timer = t;
}

struct Query {
    int l,r,id;
};
 
const int B = 100;
vi a(N),b(N);
int L = 0,R;


void fix(int l,int r) {
    if (l != L) {
        assert(l >= L);
        while (L < l) {
            L++;
            unite(a[L],b[L]);
        }
    }
    else {
        assert(r <= R);
        while (R > r) {
            R--;
            unite(a[R],b[R]);
        }
    }
}

void solve() {
    cin >> n >> m >> q;
    R = m+1;
    for (int i=1;i<=n;i++) dad[i] = i,d[i] = 0;
    vi ans(q+1);
    for (int i=1;i<=m;i++) cin >> a[i] >> b[i];
    vector<Query> qs(q+1);
    for (int i=1;i<=q;i++) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].l--,qs[i].r++;
        qs[i].id = i;
    }
    int blocks = (m+B)/B;
    vector<Query> queries[blocks+1];
    for (int i=1;i<=q;i++) queries[(qs[i].l+B-1)/B].push_back(qs[i]);
    for (int i=1;i<=blocks;i++) {
        if (queries[i].empty()) continue;
        sort(all(queries[i]),[&](const Query& q1,const Query& q2) {
            return q1.r > q2.r;
        });
        fix((i-1)*B,R);
        for (int j = 0;j<queries[i].size();j++) {
            const Query& Q = queries[i][j];
            fix(L,Q.r);
            int mytime = timer;
            fix(Q.l,R);
            if (bipartite) ans[Q.id] = 0;
            else ans[Q.id] = 1;
            rollback(mytime);
        }
        rollback(0);
        L = 0,R = m+1;
    }
    for (int i=1;i<=q;i++) cout << ((ans[i])?"YES\n":"NO\n");

}
 
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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