Submission #1110058

#TimeUsernameProblemLanguageResultExecution timeMemory
1110058AverageAmogusEnjoyerJoker (BOI20_joker)C++17
100 / 100
1611 ms23996 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; } template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; } constexpr int nax = 200200,block_size = 450; vector<tuple<int,int,int>> queries[block_size]; // r,l,idx vector<bool> ans; int edges[nax][2]; int n,m; bool pref[nax]; bool suff[nax]; bool pref_suff[nax]; struct dsu_save { int x,y,lzx,lzy,szx,szy,parx,pary; }; struct DSU { int lz[nax]; int par[nax]; int sz[nax]; dsu_save stk[nax]; // avoid allocating a lot of memory on heap -- better to allocate initially on stack int T = 0; void init() { for (int i = 0; i < nax; i++) lz[i] = 0, par[i] = i, sz[i] = 1; } int get(int x,int &cx) { while(1) { cx ^= lz[x]; if (x == par[x]) return x; x = par[x]; } } bool need_reset = 0; bool unite(int x,int y) { assert(!need_reset); int cx = 0,cy = 0; int px = get(x,cx), py = get(y,cy); if (sz[px] < sz[py]) swap(px,py), swap(cx,cy); stk[T++] = {px,py,lz[px],lz[py],sz[px],sz[py],par[px],par[py]}; if (cx == cy) { if (px == py) { need_reset = 1; return 1; } else { lz[py] ^= 1; sz[px] += sz[py]; par[py] = px; } } else { if (px != py) { sz[px] += sz[py]; par[py] = px; } } return 0; } void rollback(int k) { need_reset = 0; assert(T >= k); while(k--) { auto &c = stk[--T]; lz[c.x] = c.lzx,lz[c.y] = c.lzy,par[c.x] = c.parx,par[c.y] = c.pary,sz[c.x] = c.szx,sz[c.y] = c.szy; } } }; DSU dsu; bool solve_block(int block) { int current_r = m - 1; for (int i = max(0,(block - 1) * block_size); i < min(m,block * block_size); i++) { if (dsu.unite(edges[i][0],edges[i][1])) { for (int B = block; B < block_size; B++) for (auto &[r,l,idx]: queries[B]) ans[idx] = 1; return 1; } } for (int i = 0, K = 0; i < queries[block].size();) { auto &[r,l,idx] = queries[block][i]; while(K < queries[block].size() && get<0>(queries[block][K]) == r && get<1>(queries[block][K]) == l) K++; bool RW = 0; if (pref[l] || suff[m - r] || pref_suff[min(l,m - r)]) { RW = 1; } else { while(current_r >= r) { if (dsu.unite(edges[current_r][0],edges[current_r][1])) { for (int j = i; j < queries[block].size(); j++) { int idx2 = get<2>(queries[block][j]); ans[idx2] = 1; } dsu.rollback(m - current_r); // potrebbero essere necessari dei +- 1 return 0; } current_r--; } --l; int inserted = 0; while(l >= block * block_size) { // devo inserirlo inserted++; // cout << "edge index: " << l + 1 << endl; if (dsu.unite(edges[l][0],edges[l][1])) { RW = 1; break; } l--; } dsu.rollback(inserted); } while(i < K) { ans[get<2>(queries[block][i])] = RW; i++; } } dsu.rollback(m - current_r - 1); return 0; } bool res[block_size][block_size]; void precomp() { dsu.init(); for (int block = 0; block < block_size; block++) { bool flag = 0; int ins = 0; for (int other = block_size - 1; other > block && !flag; other--) { int l = other * block_size; // questo e' acceso! int r = min(m,(other + 1) * block_size); --r; while(r >= l) { ins++; if (dsu.unite(edges[r][0],edges[r][1])) { for (int O = other; O > block; O--) res[block][O] = 1; flag = 1; dsu.rollback(ins); ins = 0; break; } r--; } } dsu.rollback(ins); assert(dsu.T == min(m,block * block_size)); for (int i = block_size * block; i < (block + 1) * block_size && i < m; i++) { if (dsu.unite(edges[i][0],edges[i][1])) { for (int BL = block + 1; BL < block_size; BL++) for (int BR = BL + 1; BR < block_size; BR++) res[BL][BR] = 1; dsu.rollback(i + 1); assert(dsu.T == 0); return; } } } assert(dsu.T == m); dsu.rollback(m); } bool FOUND_GLOBAL = 0; void precomp2() { dsu.init(); int i = 1; while(i <= m && !dsu.unite(edges[i - 1][0],edges[i - 1][1])) i++; FOUND_GLOBAL = (i != m + 1); if (!FOUND_GLOBAL) { dsu.rollback(m); return; } dsu.rollback(i); while(i <= m) pref[i++] = 1; i = 1; while(i <= m && !dsu.unite(edges[m - i][0],edges[m - i][1])) i++; dsu.rollback(i); assert(dsu.T == 0); while(i <= m) suff[i++] = 1; int l = 0, r = m - 1; int p = 0; bool f = 0; while(l < r) { p++; if (dsu.unite(edges[l][0],edges[l][1])) { f = 1; break; } p++; if (dsu.unite(edges[r][0],edges[r][1])) { f = 1; break; } l++,r--; } dsu.rollback(p); assert(dsu.T == 0); p = (p + 1) / 2; while(p <= m) pref_suff[p++] = f; } vector<bool> trova_cicli(int N, int M, int Q, vector<int> A, vector<int> B, vector<int> L, vector<int> R) { n = N, m = M; for (int i = 0; i < M; i++) edges[i][0] = A[i],edges[i][1] = B[i]; // precomp(); too slow for now precomp2(); dsu.init(); ans.resize(Q); if (!FOUND_GLOBAL) return ans; for (int i = 0; i < Q; i++) queries[L[i] / block_size].emplace_back(R[i],L[i],i); for (int i = 0; i < block_size; i++) sort(queries[i].rbegin(),queries[i].rend()); for (int i = 0; i < block_size; i++) if (solve_block(i)) break; return ans; } int main() { int N,M,Q; cin >> N >> M >> Q; vector<int> A(M),B(M),L(Q),R(Q); for (int i = 0; i < M; i++) { cin >> A[i] >> B[i]; --A[i],--B[i]; } for (int i = 0; i < Q; i++) { cin >> L[i] >> R[i]; --L[i]; } auto risposta = trova_cicli(N,M,Q,A,B,L,R); for (int i = 0; i < Q; i++) cout << (risposta[i] ? "YES" : "NO") << "\n"; }

Compilation message (stderr)

Joker.cpp: In function 'bool solve_block(int)':
Joker.cpp:85:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0, K = 0; i < queries[block].size();) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         while(K < queries[block].size() && get<0>(queries[block][K]) == r && get<1>(queries[block][K]) == l) K++;
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:94:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                     for (int j = i; j < queries[block].size(); j++) {
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~~~
#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...