Submission #1093481

#TimeUsernameProblemLanguageResultExecution timeMemory
1093481duckindogJoker (BOI20_joker)C++17
0 / 100
155 ms12740 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10; int n, m, q; struct Edge { int u, v; friend istream& operator >> (istream& is, auto& rhs) { return is >> rhs.u >> rhs.v; } } edge[N]; int id[N], cnt; bool mk[N]; vector<tuple<int, int, int, int, int, int>> undo; int root(int u) { return id[u] < 0 ? u : root(id[u]); } bool chk(int u) { return id[u] < 0 ? mk[u] : mk[u] ^ chk(id[u]); } void add(int u, int v) { int oU = u, oV = v; u = root(u); v = root(v); if (u == v) { undo.emplace_back(0, 0, 0, 0, 0, cnt); cnt += chk(u) == chk(v); return; } if (id[u] > id[v]) swap(u, v); undo.emplace_back(u, id[u], v, id[v], mk[v], cnt); mk[v] ^= (chk(oU) == chk(oV)); id[u] += id[v]; id[v] = u; } void rollBack() { auto [u, idU, v, idV, mkV, pCnt] = undo.back(); undo.pop_back(); id[u] = idU; id[v] = idV; mk[v] = mkV; cnt = pCnt; } int f[N]; void dnc(int l, int r, int lt, int rt) { if (l > r) return; int mid = (l + r) >> 1; auto& ret = f[mid]; for (int i = l; i < mid; ++i) add(edge[i].u, edge[i].v); for (int i = rt; i >= max(mid + 1, lt); --i) add(edge[i].u, edge[i].v); for (int i = max(mid + 1, lt); i <= rt; ++i) { if (cnt) ret = i - 1; rollBack(); } if (cnt) ret = rt; int nxtR = (!ret ? max(mid + 1, lt) : ret), nxtL = (!ret ? mid : ret); add(edge[mid].u, edge[mid].v); dnc(mid + 1, r, nxtR, rt); for (int i = mid; i >= l; --i) rollBack(); for (int i = rt; i > nxtL; --i) add(edge[i].u, edge[i].v); dnc(l, mid - 1, lt, nxtL); for (int i = rt; i > nxtL; --i) rollBack(); } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> q; for (int i = 1; i <= m; ++i) cin >> edge[i]; memset(id, -1, sizeof id); dnc(1, n, 1, m); while (q--) { int l, r; cin >> l >> r; cout << (r <= f[l] ? "YES" : "NO") << "\n"; } }

Compilation message (stderr)

Joker.cpp:9:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    9 |   friend istream& operator >> (istream& is, auto& rhs) {
      |                                             ^~~~
#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...