Submission #1091416

#TimeUsernameProblemLanguageResultExecution timeMemory
1091416andrei_iorgulescuJoker (BOI20_joker)C++14
0 / 100
2031 ms4944 KiB
#include <bits/stdc++.h> using namespace std; int n, m, q; int u[200005], v[200005]; int rmin[200005]; pair<int, int> t[200005]; int sz[200005]; bool bip[200005]; int cnt_bad; int curi; struct ura { int tip;///0 pentru p1.first != p2.first, 1 pentru celalalt int idx = 0, x = 0, y = 0; bool bipant = false; }; vector<ura> op; pair<int, int> par(int x) { int s1 = 0; while (t[x].first != x) { s1 += t[x].second; x = t[x].first; } return make_pair(x, s1); } void join(int idx, int x, int y) { //cout << idx << ' ' << x << ' ' << y << endl; pair<int,int> p1 = par(x); pair<int,int> p2 = par(y); //cout << x << ' ' << y << endl; if (p1.first != p2.first) { if (sz[p1.first] < sz[p2.first]) swap(p1, p2); //cout << "c1" << endl; t[p2.first] = {p1.first, (1 + p1.second + p2.second) % 2}; //sz[x] += sz[y]; /*ura aux; aux.tip = 0; aux.idx = idx, aux.x = x, aux.y = y; aux.bipant = bip[x];*/ /*if (bip[x] == false and bip[y] == false){ cnt_bad--;} if (bip[y] == false) bip[x] = false;*/ //op.push_back(aux); } else { /*ura aux; aux.tip = 1; aux.idx = idx; aux.x = x; aux.y = y; aux.bipant = bip[x];*/ if (p1.second % 2 == p2.second % 2 and bip[x] == true) { //cout << "cmon" << p1.first << endl; //bip[x] = false; cnt_bad++; } //op.push_back(aux); } } void und(ura uf) { //cout << "und" << uf.idx << endl; if (uf.tip == 0) { if (bip[uf.y] == false and uf.bipant == false) cnt_bad++; bip[uf.x] = uf.bipant; sz[uf.x] -= sz[uf.y]; t[uf.y] = {uf.y, 0}; } else { if (bip[uf.x] != uf.bipant) cnt_bad--; bip[uf.x] = uf.bipant; } } bool cmp(ura A, ura B) { if ((A.idx < curi and B.idx >= curi) or (A.idx >= curi and B.idx < curi)) return A.idx < B.idx; else if (A.idx < curi) return A.idx < B.idx; else return A.idx > B.idx; } void undo(int idx) { //cout << "u" << idx << endl; vector<ura> cur; int cate = 0; while (true) { cur.push_back(op.back()); op.pop_back(); cate++; if (cur.back().idx == idx) break; } while (cate != 0 and !op.empty()) { cur.push_back(op.back()); op.pop_back(); cate--; } for (auto it : cur) und(it); sort(cur.begin(), cur.end(), cmp); for (auto it : cur) if (it.idx != idx) join(it.idx, u[it.idx], v[it.idx]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> q; for (int i = 1; i <= m; i++) cin >> u[i] >> v[i]; for (int i = 1; i <= n; i++) { t[i] = {i, 0}; sz[i] = 1; bip[i] = true; } /*for (int i = 1; i <= m; i++) join(i, u[i], v[i]); //cout << cnt_bad << endl; if (cnt_bad == 0) { for (int i = 1; i <= q; i++) { int x, y; cin >> x >> y; cout << "NO\n"; } return 0; } int r = 0; for (int i = 1; i <= m; i++) { curi = i; while (r < m and cnt_bad > 0) { r++; undo(r); } if (cnt_bad != 0) { rmin[i] = m + 1; continue; } rmin[i] = r; join(i, u[i], v[i]); } //for (int i = 1; i <= m; i++) // cout << rmin[i] << ' '; //cout << endl; for (int i = 1; i <= q; i++) { int x, y; cin >> x >> y; if (rmin[x] > y) cout << "YES\n"; else cout << "NO\n"; }*/ rmin[1] = 1; for (int i = m; i >= 1; i--) { join(i, u[i], v[i]); if (cnt_bad != 0) { rmin[1] = i; break; } } for (int i = 1; i <= q; i++) { int x, y; cin >> x >> y; if (y < rmin[x]) cout << "YES\n"; else cout << "NO\n"; } return 0; } /** deci teoretic daca bag elementele de la 1 la N, apoi fac two pointers-ul, o sa cam am queue-like undoing pe DSU, pe care tin si ceva de bipartit **/
#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...