Submission #1049710

#TimeUsernameProblemLanguageResultExecution timeMemory
1049710shiomusubi496Joker (BOI20_joker)C++17
71 / 100
2060 ms19736 KiB
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i) #define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i) #define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i) #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) using namespace std; using ll = long long; template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; } template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; } class UndoableUF { bool flag = true; vector<int> par, wei; vector<tuple<int, int, int, bool>> history; public: UndoableUF(int n_) : par(n_, -1), wei(n_, 0) {} int find(int x) { return par[x] < 0 ? x : find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } int weight(int x) { return par[x] < 0 ? wei[x] : wei[x] ^ weight(par[x]); } bool merge(int x, int y) { int xr = find(x), yr = find(y); int w = weight(x) ^ weight(y); x = xr, y = yr; history.emplace_back(x, par[x], wei[x], flag); history.emplace_back(y, par[y], wei[y], flag); if (x == y) { if (w == 0) flag = false; return false; } if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; wei[y] = 1 ^ w; return true; } int find2(int x) { if (par[x] < 0) return x; int r = find2(par[x]); // history.emplace_back(x, par[x], wei[x], flag); wei[x] ^= wei[par[x]]; return par[x] = r; } bool same2(int x, int y) { return find2(x) == find2(y); } bool merge2(int x, int y) { int xr = find2(x), yr = find2(y); int w = wei[x] ^ wei[y]; x = xr, y = yr; // history.emplace_back(x, par[x], wei[x], flag); // history.emplace_back(y, par[y], wei[y], flag); if (x == y) { if (w == 0) flag = false; return false; } if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; wei[y] = 1 ^ w; return true; } void undo() { auto [x, px, wx, _] = history.back(); history.pop_back(); auto [y, py, wy, f] = history.back(); history.pop_back(); par[x] = px; par[y] = py; wei[x] = wx; wei[y] = wy; flag = f; } void snapshot() { history.clear(); } void rollback() { while (!history.empty()) { auto [x, px, wx, f] = history.back(); history.pop_back(); par[x] = px; wei[x] = wx; flag = f; } } bool is_bip() { return flag; } }; int main() { int N, M, Q; cin >> N >> M >> Q; vector<pair<int, int>> A(M); rep (i, M) { cin >> A[i].first >> A[i].second; --A[i].first, --A[i].second; } vector<array<int, 3>> B(Q); rep (i, Q) { cin >> B[i][0] >> B[i][1]; --B[i][0]; B[i][2] = i; } static constexpr int block = 470; sort(all(B), [&](auto a, auto b) { if (a[0] / block != b[0] / block) return a[0] < b[0]; return a[1] > b[1]; }); vector<bool> ans(Q); int curl = block, curr = M; UndoableUF uf(N); bool f = false; for (auto [l, r, k] : B) { if (f) { ans[k] = false; continue; } while (curl <= l) { uf.rollback(); rep2 (i, curl - block, curl) { if (i >= M) break; uf.merge(A[i].first, A[i].second); } uf.snapshot(); if (!uf.is_bip()) { ans[k] = false; f = true; break; } curl += block; curr = M; } if (f) continue; assert(curr >= r); rrep2 (i, r, curr) { uf.merge(A[i].first, A[i].second); } curr = r; rep2 (i, curl - block, l) { uf.merge(A[i].first, A[i].second); } ans[k] = uf.is_bip(); rep2 (i, curl - block, l) uf.undo(); } rep (i, Q) puts(ans[i] ? "NO" : "YES"); }
#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...