Submission #1091408

#TimeUsernameProblemLanguageResultExecution timeMemory
1091408andrei_iorgulescuJoker (BOI20_joker)C++14
0 / 100
57 ms12624 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]; vector<int> g[200005]; int cnt_bad = 0; 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 x, int y) { pair<int,int> p1 = par(x); pair<int,int> p2 = par(y); if (p1.first != p2.first) { t[p2.first] = make_pair(p1.first, (1 + p1.second + p2.second)); } else { if (p1.second % 2 == p2.second % 2) cnt_bad++; } } 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], g[u[i]].push_back(v[i]), g[v[i]].push_back(u[i]); for (int i = 1; i <= n; i++) t[i] = {i, 0}; rmin[1] = 1; for (int i = m; i >= 1; i--) { join(u[i], v[i]); if (cnt_bad != 0) { rmin[1] = i + 1; 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; } ///wtfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff /** 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...