| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 911446 |
2024-01-19T00:47:14 Z |
NK_ |
Joker (BOI20_joker) |
C++17 |
|
75 ms |
30784 KB |
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
template<class T> using V = vector<T>;
using vi = V<int>;
struct DSU {
vi e, p; V<array<int, 7>> ed;void init(int N) { e = vi(N, -1); p = vi(N, 0); }
int get(int x) { return e[x] < 0 ? x : get(e[x]); }
int parity(int x) { return e[x] < 0 ? 0 : p[x] ^ parity(e[x]); }
bool unite(int x, int y, int t) {
int rx = get(x), ry = get(y);
int px = parity(x), py = parity(y);
// cout << x << " " << y << " " << t << endl;
// cout << rx << " " << rx << " --> " << px << " " << py << endl;
if (rx == ry) {
if (px == py) return 0;
ed.pb({-1, -1, -1, -1, -1, -1}); return 1;
}
if (e[rx] > e[ry]) swap(rx, ry);
ed.pb({rx, ry, e[rx], e[ry], p[rx], p[ry], t});
e[rx] += e[ry]; e[ry] = rx; p[ry] = px ^ py ^ 1; return 1;
}
bool rollback(int T) {
if (size(ed) == 0) return 0;
auto [rx, ry, erx, ery, prx, pry, t] = ed.back();
if (t < T) return 0;
ed.pop_back();
if (rx == -1) return 1;
e[rx] = erx, p[rx] = prx;
e[ry] = ery, p[ry] = pry;
return 1;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, Q; cin >> N >> M >> Q;
V<array<int, 2>> E(M); for(auto& x : E) { cin >> x[0] >> x[1]; --x[0], --x[1]; }
vi lst(M); // lst r where when [l, r] is removed the graph is bipartite
DSU D; D.init(N);
int T = 0;
function<void(int, int, int, int)> dnc = [&](int l, int r, int lx, int rx) {
if (l > r) return;
int mid = (l + r) / 2;
// compute lst_mid
++T;
bool ok = 1;
// cout << "HELLO" << endl;
for(int i = l; i < mid; i++) {
ok &= D.unite(E[i][0], E[i][1], T);
// cout << ok << endl;
if (!ok) break;
}
// cout << "START " << ok << endl;
// for(auto e : D.ed) {
// cout << e[0] << " <-> " << e[1] << endl;
// }
if (!ok) lst[mid] = rx;
else {
lst[mid] = rx - 1;
while(D.unite(E[lst[mid]][0], E[lst[mid]][1], T)) lst[mid]--;
}
// cout << "MID" << endl;
// for(auto e : D.ed) {
// cout << e[0] << " <-> " << e[1] << endl;
// }
while(D.rollback(T));
--T;
// cout << l << " " << mid << " " << r << " " << lst[mid] << endl;
// cout << lx << " " << rx << endl;
// for(auto e : D.ed) {
// cout << e[0] << " <-> " << e[1] << endl;
// }
// cout << "DONE" << endl;
// [l, mid - 1]
++T;
for(int i = rx - 1; i > lst[mid]; i--) D.unite(E[i][0], E[i][1], T);
dnc(l, mid - 1, lx, lst[mid] + 1);
while(D.rollback(T));
--T;
// [mid + 1, r]
++T;
ok = 1;
for(int i = l; i <= mid; i++) ok &= D.unite(E[i][0], E[i][1], T);
if (ok) dnc(mid + 1, r, max(mid + 1, lst[mid]), rx);
else for(int i = mid + 1; i <= r; i++) lst[i] = rx;
while(D.rollback(T));
--T;
};
dnc(0, M - 1, 0, M);
// for(int i = 0; i < M; i++) {
// lst[i] = max(lst[i], lst[i-1]);
// cout << i << " => " << lst[i] << nl;
// }
for(int i = 0; i < Q; i++) {
int l, r; cin >> l >> r; --l, --r;
cout << (lst[l] <= r ? "NO" : "YES") << nl;
}
exit(0-0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
75 ms |
14780 KB |
Output is correct |
| 4 |
Runtime error |
57 ms |
30784 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
