Submission #882416

#TimeUsernameProblemLanguageResultExecution timeMemory
882416kh0iJoker (BOI20_joker)C++17
100 / 100
246 ms45896 KiB
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) #endif using ll = long long; using pii = pair<int, int>; #define F first #define S second #define sz(x) (int)((x).size()) #define all(x) (x).begin(), (x).end() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll get_rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll> (l, r)(rng); } const int N = 2e5 + 3; int n, m, q, L[N], R[N]; vector<pii> g[N]; pii e[N]; // contain no odd cycle -> bipartite graph namespace Sub12{ bool valid_input(){ return n <= 2000 and m <= 2000 and q <= 2000; } int vis[N]; bool dfs(int u, int l, int r, int col){ bool ok = 1; vis[u] = col; for(auto [v, id] : g[u]){ if(l <= id and id <= r) continue; if(vis[v]) ok &= (vis[u] != vis[v]); else ok &= dfs(v, l, r, col ^ 3); } return ok; } void solve(){ for(int i = 1; i <= q; ++i){ bool bipartite = 1; for(int u = 1; u <= n; ++u) vis[u] = 0; for(int u = 1; u <= n; ++u){ if(!vis[u]) bipartite &= dfs(u, L[i], R[i], 1); } cout << (bipartite ? "NO\n" : "YES\n"); } } } struct DSU{ bool bipartite = 1; vector<pii> p; int n; void init(int _n){ n = _n; p.resize(n + 2); for(int i = 1; i <= n; ++i) p[i] = {i, 0}; } pii find_set(int u){ if(u != p[u].F){ int parity = p[u].S; p[u] = find_set(p[u].F); p[u].S ^= parity; } return p[u]; } void add_edge(int u, int v){ pii pu = find_set(u); u = pu.F; pii pv = find_set(v); v = pv.F; int x = pu.S, y = pv.S; if(u == v){ bipartite &= (x != y); return; } p[v] = {u, x ^ y ^ 1}; } }; namespace Sub34{ bool valid_input(){ bool ok = 1; for(int i = 1; i <= q; ++i) ok &= (L[i] <= 200); return ok; } int ans[N]; vector<pii> d[N]; void solve(){ for(int i = 1; i <= q; ++i){ d[L[i]].push_back({R[i], i}); } for(int i = 1; i <= min(200, m); ++i){ DSU dsu; dsu.init(n); for(int j = 1; j < i; ++j){ dsu.add_edge(e[j].F, e[j].S); } sort(all(d[i]), [](pii &x, pii &y) -> bool{ return x.F < y.F; }); for(int j = m; j >= i; --j){ while(!d[i].empty() and d[i].back().F == j){ ans[d[i].back().S] = dsu.bipartite; d[i].pop_back(); } dsu.add_edge(e[j].F, e[j].S); } } for(int i = 1; i <= q; ++i) cout << (ans[i] ? "NO\n" : "YES\n"); } } struct DSU_Rollback{ vector<int> p, c; vector<array<int, 5>> op; bool bipartite = 1; void init(int n){ p.clear(); p.resize(n + 2, -1); c.clear(); c.resize(n + 2, 0); } pii get(int x){ int d = 0; while(p[x] >= 0){ d ^= c[x]; x = p[x]; } return {x, d}; } void join_sets(int u, int v){ debug("JOIN", u, v); pii pu = get(u), pv = get(v); op.push_back({pu.F, pv.F, p[pu.F], p[pv.F], bipartite}); if(pu.F == pv.F){ bipartite &= (pu.S != pv.S); return; } if(p[pu.F] > p[pv.F]) swap(pu, pv); p[pu.F] += p[pv.F]; p[pv.F] = pu.F; c[pv.F] = pu.S ^ pv.S ^ 1; return; } void rollback(){ debug("ROLL"); array<int, 5> x = op.back(); op.pop_back(); if(x[0] == -1) return; p[x[0]] = x[2], p[x[1]] = x[3]; bipartite = x[4]; } }; namespace Sub5{ bool valid_input(){ return q <= 2000; } int B, add_time[N]; vector<int> blk[N]; int ans[N]; void solve(){ B = m / sqrt(q); debug(B); for(int i = 1; i <= q; ++i) blk[(L[i] + B - 1) / B].push_back(i); for(int bl = 1; bl < N; ++bl){ if(blk[bl].empty()) continue; vector<int> &d = blk[bl]; debug(d); sort(all(d), [](int &x, int &y) -> bool { return R[x] < R[y]; }); DSU_Rollback dsu; dsu.init(n); int timer = 0; int U = (bl - 1) * B + 1; debug(U); for(int i = 1; i < U; ++i) dsu.join_sets(e[i].F, e[i].S); for(int i = m; i > R[d.front()]; --i) dsu.join_sets(e[i].F, e[i].S); int cur = R[d.front()] + 1; for(int x : d){ debug(L[x], R[x], cur); while(cur <= R[x]){ dsu.rollback(); ++cur; } int last = timer; debug(last); for(int i = U; i < L[x]; ++i) dsu.join_sets(e[i].F, e[i].S); ans[x] = dsu.bipartite; for(int i = U; i < L[x]; ++i) dsu.rollback(); } } for(int i = 1; i <= q; ++i) cout << (ans[i] ? "NO\n" : "YES\n"); } }; namespace Sub6{ DSU_Rollback dsu; int last[N]; void calc(int l, int r, int optL, int optR){ int mid = (l + r) >> 1; for(int i = l; i < mid; ++i) dsu.join_sets(e[i].F, e[i].S); int opt = optR; while(dsu.bipartite) dsu.join_sets(e[opt].F, e[opt].S), --opt; last[mid] = opt; for(int i = opt + 1; i <= optR; ++i) dsu.rollback(); dsu.join_sets(e[mid].F, e[mid].S); if(mid < r) calc(mid + 1, r, opt, optR); for(int i = l; i <= mid; ++i) dsu.rollback(); for(int i = optR; i > opt; --i) dsu.join_sets(e[i].F, e[i].S); if(l < mid) calc(l, mid - 1, optL, opt); for(int i = opt + 1; i <= optR; ++i) dsu.rollback(); } void solve(){ dsu.init(n); calc(1, m, 1, m); for(int i = 1; i <= m; ++i) debug(i, last[i]); for(int i = 1; i <= q; ++i) cout << (last[L[i]] >= R[i] ? "YES\n" : "NO\n"); } } void solve(){ cin >> n >> m >> q; for(int i = 1; i <= m; ++i){ int u, v; cin >> u >> v; g[u].push_back({v, i}); g[v].push_back({u, i}); e[i] = {u, v}; } for(int i = 1; i <= q; ++i) cin >> L[i] >> R[i]; Sub6::solve(); } int32_t main() { cin.tie(nullptr)->sync_with_stdio(0); #define task "nohome" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++i){ // cout << "Case #" << i << ": "; solve(); } #ifdef LOCAL cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n"; #endif return 0; }

Compilation message (stderr)

Joker.cpp: In function 'void Sub5::solve()':
Joker.cpp:233:21: warning: unused variable 'last' [-Wunused-variable]
  233 |                 int last = timer;
      |                     ^~~~
Joker.cpp: In function 'int32_t main()':
Joker.cpp:309:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  309 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:310:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  310 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...