Submission #1199871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199871		dosts	Joker (BOI20_joker)	C++20	0 / 100	1 ms	2624 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;
};
 
vi a(N),b(N);
int L = 0,R;


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

vi calc(N);
void dnq(int l,int r,int optl,int optr) {
    if (l > r) return;
    if (!bipartite) {
        for (int j = l;j<=r;j++) calc[j] = m+1;
        return;
    }
    int mid = (l+r) >> 1;
    int oldtime = timer;
    fix(mid-1,R);
    int ans = m+1;
    for (int i = optr;i>=optl && i > mid;i--) {
        fix(L,i);
        if (!bipartite) {
            ans = i;
            break;
        }
    }
    calc[mid] = ans;
    rollback(timer-oldtime);
    oldtime = timer;
    fix(L,ans+1);
    fix(l-1,R);
    dnq(l,mid-1,optl,ans);
    rollback(timer-oldtime);
    oldtime = timer;
    fix(mid,R);
    fix(L,optr+1);
    dnq(mid+1,r,ans,optr);
    rollback(timer-oldtime);
}

void solve() {
    cin >> n >> m >> q;
    R = m+1;
    for (int i=1;i<=n;i++) dad[i] = {i,0},sz[i] = 1;
    for (int i=1;i<=m;i++) cin >> a[i] >> b[i];
    dnq(1,m,1,m);
    for (int i=1;i<=q;i++) {
        int l,r;
        cin >> l >> r;
        if (calc[l] <= r) cout << "NO\n";
        else cout << "YES\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