| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1049364 |
2024-08-08T17:14:22 Z |
duckindog |
Joker (BOI20_joker) |
C++17 |
|
191 ms |
8824 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200'000 + 10;
int n, m, q;
pair<int, int> edge[N];
vector<tuple<int, int, int, int>> undo;
int id[N], cnt;
int root(int u) { return id[u] < 0 ? u : root(id[u]); }
inline void add(int u, int v) {
u = root(u); v = root(v);
if (u == v) {
cnt += 1;
undo.emplace_back(0, -1, 0, -1);
return;
}
if (id[u] > id[v]) swap(u, v);
undo.emplace_back(u, id[u], v, id[v]);
id[u] += id[v];
id[v] = u;
}
inline void rollBack() {
auto [u, idu, v, idv] = undo.back(); undo.pop_back();
cnt -= !u;
id[u] = idu;
id[v] = idv;
}
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].first, edge[i].second);
for (int i = rt; i >= max(mid + 1, lt); --i) add(edge[i].first, edge[i].second);
for (int i = max(mid + 1, lt); i <= rt; ++i) {
const auto& [u, v] = edge[i];
if (cnt) ret = i - 1;
rollBack();
} if (cnt) ret = rt;
add(edge[mid].first, edge[mid].second);
dnc(mid + 1, r, !ret ? lt : ret, rt);
for (int i = l; i <= mid; ++i) rollBack();
for (int i = rt; i > (!ret ? rt : ret); --i) add(edge[i].first, edge[i].second);
dnc(l, mid - 1, lt, (!ret ? rt : ret));
for (int i = rt; i > (!ret ? rt : ret); --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].first >> edge[i].second;
memset(id, -1, sizeof id);
dnc(1, m, 1, m);
while (q--) {
int l, r; cin >> l >> r;
cout << (r <= f[l] ? "YES" : "NO") << "\n";
}
}
Compilation message
Joker.cpp: In function 'void dnc(int, int, int, int)':
Joker.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid = l + r >> 1;
| ~~^~~
Joker.cpp:41:17: warning: unused structured binding declaration [-Wunused-variable]
41 | const auto& [u, v] = edge[i];
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
83 ms |
8660 KB |
Output is correct |
| 4 |
Incorrect |
191 ms |
8824 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
