Submission #765947

#TimeUsernameProblemLanguageResultExecution timeMemory
765947HegdahlJoker (BOI20_joker)C++17
100 / 100
1539 ms12532 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; struct UnionFind { vector<int> parent_or_neg_size, edge_parity; struct UndoInfo { int i, j, j_sz; }; vector<UndoInfo> undo_info; UnionFind(int n) : parent_or_neg_size(n, -1), edge_parity(n, 0) {} pair<int, int> find_root_and_parity(int i) { int parity = 0; while (parent_or_neg_size[i] >= 0) { parity ^= edge_parity[i]; i = parent_or_neg_size[i]; } return {i, parity}; } int path_compressing_find(int i) { if (parent_or_neg_size[i] < 0) { edge_parity[i] = 0; return i; } int new_parent = path_compressing_find(parent_or_neg_size[i]); edge_parity[i] ^= edge_parity[parent_or_neg_size[i]]; return parent_or_neg_size[i] = new_parent; } enum UniteResult { NO_CYCLE, EVEN_CYCLE, ODD_CYCLE }; UniteResult persistent_unite(int i, int j, bool new_edge_parity = true) { auto [root_i, parity_i] = find_root_and_parity(i); auto [root_j, parity_j] = find_root_and_parity(j); if (root_i == root_j) { undo_info.push_back({0, 0, 0}); if (parity_i ^ parity_j ^ new_edge_parity) { return ODD_CYCLE; } else { return EVEN_CYCLE; } } if (parent_or_neg_size[root_i] > parent_or_neg_size[root_j]) { swap(root_i, root_j); swap(parity_i, parity_j); } undo_info.push_back({ .i = root_i, .j = root_j, .j_sz = parent_or_neg_size[root_j], }); parent_or_neg_size[root_i] += parent_or_neg_size[root_j]; parent_or_neg_size[root_j] = root_i; edge_parity[root_j] = parity_i ^ parity_j ^ new_edge_parity; return NO_CYCLE; } UniteResult fast_unite(int i, int j, bool new_edge_parity = true) { int pi = path_compressing_find(i); int pj = path_compressing_find(j); if (pi == pj) { if (edge_parity[i] ^ edge_parity[j] ^ new_edge_parity) { return ODD_CYCLE; } else { return EVEN_CYCLE; } } if (parent_or_neg_size[pi] > parent_or_neg_size[pj]) { swap(pi, pj); swap(i, j); } parent_or_neg_size[pi] += parent_or_neg_size[pj]; parent_or_neg_size[pj] = pi; edge_parity[pj] = edge_parity[i] ^ edge_parity[j] ^ new_edge_parity; return NO_CYCLE; } void undo() { assert(!undo_info.empty()); auto [i, j, j_sz] = undo_info.back(); undo_info.pop_back(); if (i == 0 && j == 0) { return; } parent_or_neg_size[j] = j_sz; parent_or_neg_size[i] -= j_sz; } void undo_all() { while (!undo_info.empty()) { undo(); } } }; int main() { int n, m, q; cin >> n >> m >> q; vector<array<int, 2>> edges(m); for (auto &[u, v] : edges) { cin >> u >> v; --u; --v; } static constexpr auto BLOCK_SIZE = 800; std::vector<array<int, 2>> queries(q); std::vector<std::basic_string<int>> blocks((m + BLOCK_SIZE - 1) / BLOCK_SIZE); std::vector<bool> answers(q); for (int qq = 0; qq != q; ++qq) { auto &[l, r] = queries[qq]; cin >> l >> r; --l; blocks[l / BLOCK_SIZE].push_back(qq); } UnionFind uf(n); for (int lid = 0; lid != int(blocks.size()); ++lid) { uf.parent_or_neg_size.assign(n, -1); std::sort(blocks[lid].begin(), blocks[lid].end(), [&](int i, int j) { auto &[l0, r0] = queries[i]; auto &[l1, r1] = queries[j]; return r0 > r1; }); int min_l = lid * BLOCK_SIZE; bool base_has_odd_cycle = false; for (int j = 0; j != min_l; ++j) { auto [u, v] = edges[j]; if (uf.fast_unite(u, v) == UnionFind::ODD_CYCLE) { base_has_odd_cycle = true; break; } } int last_added = m; for (int qq : blocks[lid]) { auto &[l, r] = queries[qq]; while (!base_has_odd_cycle && r < last_added) { auto [u, v] = edges[--last_added]; if (uf.fast_unite(u, v) == UnionFind::ODD_CYCLE) { base_has_odd_cycle = true; } } bool has_odd_cycle = base_has_odd_cycle; for (int j = min_l; !has_odd_cycle && j != l; ++j) { auto [u, v] = edges[j]; if (uf.persistent_unite(u, v) == UnionFind::ODD_CYCLE) { has_odd_cycle = true; } } answers[qq] = has_odd_cycle; uf.undo_all(); } } for (bool answer : answers) { cout << (answer ? "YES" : "NO") << '\n'; } }
#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...