Submission #1049692

#TimeUsernameProblemLanguageResultExecution timeMemory
1049692shiomusubi496Joker (BOI20_joker)C++17
71 / 100
2087 ms20152 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 { int n; bool flag = true; vector<int> par; vector<tuple<int, int, bool>> history; public: UndoableUF(int n_) : n(n_ / 2), par(n_, -1) {} int find(int x) { return par[x] < 0 ? x : find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } bool merge(int x, int y) { x = find(x), y = find(y); history.emplace_back(x, par[x], flag); history.emplace_back(y, par[y], flag); if (x == y) return false; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; if (same(x, (x + n) % (2 * n))) flag = false; return true; } int find2(int x) { if (par[x] < 0) return x; history.emplace_back(x, par[x], flag); return par[x] = find2(par[x]); } bool same2(int x, int y) { return find2(x) == find2(y); } bool merge2(int x, int y) { x = find2(x), y = find2(y); history.emplace_back(x, par[x], flag); history.emplace_back(y, par[y], flag); if (x == y) return false; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; if (same2(x, (x + n) % (2 * n))) flag = false; return true; } void undo() { auto [x, px, _] = history.back(); history.pop_back(); auto [y, py, f] = history.back(); history.pop_back(); par[x] = px; par[y] = py; flag = f; } void snapshot() { history.clear(); } void rollback() { while (!history.empty()) { auto [x, px, f] = history.back(); history.pop_back(); par[x] = px; 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(2 * 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.merge2(A[i].first, A[i].second + N); uf.merge2(A[i].first + N, 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 + N); uf.merge(A[i].first + N, A[i].second); } curr = r; rep2 (i, curl - block, l) { uf.merge(A[i].first, A[i].second + N); uf.merge(A[i].first + N, A[i].second); } ans[k] = uf.is_bip(); rep2 (i, curl - block, l) uf.undo(), 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...