Submission #602329

#TimeUsernameProblemLanguageResultExecution timeMemory
602329OttoTheDinoJoker (BOI20_joker)C++17
100 / 100
703 ms26604 KiB
#include<bits/stdc++.h> using namespace std; #define rep(i,s,e) for (int i = s; i <= e; ++i) #define rrep(i,s,e) for (int i = s; i >= e; --i) #define fi first #define se second #define pb push_back #define len(a) (int)a.size() typedef vector<int> vi; typedef pair<int,int> ii; const int mx = 2e5; vi adj[mx+1]; int par[mx+1], h[mx+1], tp[mx+1], dp[mx+1], cnt, m; ii e[mx+1]; vector<vi> history; ii get_par (int u) { if (u==par[u]) return {u, tp[u]}; ii res = get_par (par[u]); ii ans = {res.fi, res.se^tp[u]}; return {ans}; } bool merge (int u, int v) { ii paru = get_par(u), parv = get_par(v); if (paru.fi==parv.fi) { history.pb({parv.fi, parv.fi, paru.se==parv.se, 0}); return paru.se==parv.se; } if (h[paru.fi]<h[parv.fi]) swap(paru, parv); history.pb({parv.fi, paru.fi, h[paru.fi]==h[parv.fi], parv.se==paru.se}); h[paru.fi] += h[paru.fi]==h[parv.fi]; par[parv.fi] = paru.fi; tp[parv.fi] ^= parv.se==paru.se; return 0; } int rollback (int t) { int sum = 0; while (t--) { int a = history.back()[0], b = history.back()[1], c = history.back()[2], d = history.back()[3]; history.pop_back(); if (a==b) { sum += c; continue; } par[a] = a; h[b] -= c; tp[a] ^= d; } return sum; } void go (int l1, int l2, int r1, int r2) { if (r1==r2) { rep (i,l1,l2) dp[i] = r1; return; } int lm = (l1+l2)/2, rm = r2, steps = 0; rep (i,l1,lm) { if (i) { cnt += merge(e[i].fi, e[i].se); steps++; } } bool suc = 0; if (cnt) { suc = 1; goto nxt; } while (true) { if (rm<=m) { cnt += merge(e[rm].fi, e[rm].se); steps++; } if (cnt) { suc = 1; break; } if (rm==lm+1) break; --rm; } nxt: cnt -= rollback(steps); if (!suc) { //don't need to do anything with dp[l1]...dp[lm] if (l2>=lm+1) { steps = 0; rep (i,l1,lm) { if (i) { cnt += merge(e[i].fi, e[i].se); steps++; } } go(lm+1, l2, lm+2, r2); cnt -= rollback(lm-l1); } return; } dp[lm] = rm; if (lm-1>=l1) { steps = 0; rep (i,rm+1,r2) { if (i<=m) { cnt += merge(e[i].fi, e[i].se); steps++; } } go (l1, lm-1, r1, rm); cnt -= rollback(steps); } if (l2>=lm+1) { steps = 0; rep (i,l1,lm) { if (i) { cnt += merge(e[i].fi, e[i].se); steps++; } } go (lm+1,l2,max(lm+2,r1),r2); cnt -= rollback(steps); } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >>n >> m >> q; rep (i,1,n) { par[i] = i; h[i] = 1; } rep (i,1,m) cin >> e[i].fi >> e[i].se; go (0,m,1,m+1); while (q--) { int l, r; cin >> l >> r; cout << (r<dp[l-1]?"YES":"NO") << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...