Submission #1199832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199832		dosts	Joker (BOI20_joker)	C++20	71 / 100	2095 ms	28312 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;
pii dad[N];
int sz[N];
int bipartite = 1;
int n,m,q;
pii find(int x) {
    if (x == dad[x].ff) return {x,0};
    pii f = find(dad[x].ff);
    return {f.ff,f.ss^dad[x].ss};
}
vector<pair<int*,int>> upds;
int timer = 0;
void unite(int x,int y) {
    if (!bipartite) return;
    pii a = find(x),b = find(y);
    if (a.ff == b.ff) {
        if (a.ss == b.ss) {
            ++timer;
            upds.push_back({&bipartite,1});
            bipartite = 0;
        }
        return;
    }
    if (sz[a.ff] > sz[b.ff]) swap(a,b);
    timer+=4;
    upds.push_back({&dad[a.ff].ff,dad[a.ff].ff});
    upds.push_back({&dad[a.ff].ss,dad[a.ff].ss});
    upds.push_back({&sz[a.ff],sz[a.ff]});
    upds.push_back({&sz[b.ff],sz[b.ff]});
    sz[b.ff]+=sz[a.ff];
    sz[a.ff] = 0;
    dad[a.ff].ff = b.ff;
    dad[a.ff].ss = a.ss^b.ss^1;
}

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

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


void fix(int l,int r) {
    if (l != L) {
        while (L < l) {
            L++;
            unite(a[L],b[L]);
        }
    }
    else {
        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,0},sz[i] = 1;
    int sq;
    for (int i=1;i*i<=q;i++) sq = i;
    B = (m+sq-1)/sq;
    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=0;i<=blocks;i++) {
        if (queries[i].empty()) continue;
        rollback(upds.size());
        L = 0,R = m+1;
        sort(all(queries[i]),[&](const Query& q1,const Query& q2) {
            return q1.r > q2.r;
        });
        fix(min(m,(i-1)*B),R);
        for (int j = 0;j<queries[i].size();j++) {
            const Query& Q = queries[i][j];
            fix(L,Q.r);
            int oldL = L,oldR = R;
            int mytime = timer;
            fix(Q.l,R);
            if (bipartite) ans[Q.id] = 0;
            else ans[Q.id] = 1;
            rollback(timer-mytime);
            L = oldL,R = oldR;
        }
    }
    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: 8 / 8
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 22 / 22
• Subtask 5: 0 / 29
• Subtask 6: 6 / 6