| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1115802 |
2024-11-21T01:29:38 Z |
jay22 |
간선 파괴 (GA5_destroy) |
C++17 |
|
29 ms |
5920 KB |
#include <iostream>
#include <cstring>
const int V_LEN = 702;
const int E_LEN = 123460;
int V, E, Q;
int u[E_LEN], v[E_LEN];
int pre[E_LEN], nxt[E_LEN];
int L[V_LEN], R[V_LEN];
int p[V_LEN];
int c[V_LEN][V_LEN];
int find(int i) { return p[i] < 0 ? i : p[i] = find(p[i]); }
int join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return 0;
if (p[a] < p[b]) p[a] += p[b], p[b] = a;
else p[b] += p[a], p[a] = b;
return 1;
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> V >> E;
memset(p, -1, sizeof p);
for (int i = 1; i <= E; ++i) {
std::cin >> u[i] >> v[i];
pre[i] = pre[i - 1];
if (join(u[i], v[i])) L[pre[i]++] = i;
}
memset(p, -1, sizeof p);
for (int i = E; i > 0; --i) {
nxt[i] = nxt[i + 1];
if (join(u[i], v[i])) R[nxt[i]++] = i;
}
for (int i = 0; i <= pre[E]; ++i) {
memset(p, -1, sizeof p);
c[i][0] = i;
for (int j = 0; j < i; ++j) join(u[L[j]], v[L[j]]);
for (int j = 0; j < pre[E]; ++j) {
if (join(u[R[j]], v[R[j]])) c[i][j + 1]++;
c[i][j + 1] += c[i][j];
}
}
/*std::cout << "pre: ";
for (int i = 0; i < pre[E]; ++i) std::cout << L[i] << ' ';
std::cout << '\n';
std::cout << "nxt: ";
for (int i = 0; i < pre[E]; ++i) std::cout << R[i] << ' ';
std::cout << '\n';
for (int i = 0; i <= pre[E]; ++i) {
for (int j = 0; j <= pre[E]; ++j) {
std::cout << c[i][j] << ' ';
}
std::cout << '\n';
}*/
std::cin >> Q;
for (int q = 0, l, r; q < Q; ++q) {
std::cin >> l >> r;
l = pre[l - 1], r = nxt[r + 1];
// std::cout << "query: " << l << ' ' << r << ' ';
std::cout << V - c[l][r] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2896 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2788 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2896 KB |
Output is correct |
| 4 |
Correct |
9 ms |
3664 KB |
Output is correct |
| 5 |
Correct |
10 ms |
3664 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3664 KB |
Output is correct |
| 7 |
Correct |
11 ms |
3664 KB |
Output is correct |
| 8 |
Correct |
12 ms |
3812 KB |
Output is correct |
| 9 |
Correct |
4 ms |
2640 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2640 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2640 KB |
Output is correct |
| 12 |
Correct |
10 ms |
3664 KB |
Output is correct |
| 13 |
Correct |
10 ms |
3680 KB |
Output is correct |
| 14 |
Correct |
9 ms |
3832 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2640 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2640 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2640 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2640 KB |
Output is correct |
| 19 |
Correct |
3 ms |
2640 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
4348 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4176 KB |
Output is correct |
| 3 |
Correct |
28 ms |
5920 KB |
Output is correct |
| 4 |
Correct |
18 ms |
4200 KB |
Output is correct |
| 5 |
Correct |
16 ms |
3920 KB |
Output is correct |
| 6 |
Correct |
25 ms |
5712 KB |
Output is correct |
| 7 |
Correct |
23 ms |
3920 KB |
Output is correct |
| 8 |
Correct |
18 ms |
3920 KB |
Output is correct |
| 9 |
Correct |
13 ms |
3112 KB |
Output is correct |
| 10 |
Correct |
13 ms |
3188 KB |
Output is correct |
| 11 |
Correct |
16 ms |
3664 KB |
Output is correct |
| 12 |
Correct |
29 ms |
5712 KB |
Output is correct |
| 13 |
Correct |
21 ms |
4680 KB |
Output is correct |
| 14 |
Correct |
20 ms |
4688 KB |
Output is correct |
| 15 |
Correct |
15 ms |
3152 KB |
Output is correct |
| 16 |
Correct |
13 ms |
3152 KB |
Output is correct |
| 17 |
Correct |
11 ms |
3152 KB |
Output is correct |
| 18 |
Correct |
11 ms |
3152 KB |
Output is correct |
| 19 |
Correct |
8 ms |
3152 KB |
Output is correct |
| 20 |
Correct |
10 ms |
3152 KB |
Output is correct |
| 21 |
Correct |
7 ms |
2896 KB |
Output is correct |
| 22 |
Correct |
8 ms |
2896 KB |
Output is correct |
