#include <bits/stdc++.h>
using namespace std;
int par[710];
int root(int x)
{
return !par[x] ? x : (par[x] = root(par[x]));
}
bool merge(int x, int y)
{
x = root(x);
y = root(y);
if(x == y)
return 0;
par[x] = y;
return 1;
}
pair<int, int> edg[150000];
vector<pair<int, int>> seg[270000];
void init(int x, int l, int r)
{
if(l == r)
{
auto [a, b] = edg[l];
par[a] = par[b] = 0;
assert(merge(a, b));
seg[x].push_back(edg[l]);
return;
}
init(2 * x, l, (l + r) / 2);
for(auto [a, b] : seg[2 * x])
par[a] = par[b] = 0;
init(2 * x + 1, (l + r) / 2 + 1, r);
for(auto [a, b] : seg[2 * x])
if(merge(a, b))
seg[x].push_back({ a, b });
for(auto p : seg[2 * x + 1])
seg[x].push_back(p);
}
int get_val(int x, int l, int r, int s, int g)
{
if(g < l || r < s || g < s)
return 0;
if(s <= l && r <= g)
{
int c = 0;
for(auto [a, b] : seg[x])
if(merge(a, b))
c++;
return c;
}
return get_val(2 * x, l, (l + r) / 2, s, g) + get_val(2 * x + 1, (l + r) / 2 + 1, r, s, g);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
edg[i] = { x, y };
}
init(1, 1, m);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
int x, y;
scanf("%d%d", &x, &y);
memset(par, 0, sizeof par);
int r = n - get_val(1, 1, m, 1, x - 1) - get_val(1, 1, m, y + 1, m);
printf("%d\n", r);
}
return 0;
}
Compilation message
destroy.cpp: In function 'int main()':
destroy.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
destroy.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
destroy.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
destroy.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
6656 KB |
Output is correct |
2 |
Correct |
9 ms |
6656 KB |
Output is correct |
3 |
Correct |
9 ms |
6656 KB |
Output is correct |
4 |
Correct |
9 ms |
6656 KB |
Output is correct |
5 |
Correct |
10 ms |
6528 KB |
Output is correct |
6 |
Correct |
9 ms |
6656 KB |
Output is correct |
7 |
Correct |
9 ms |
6656 KB |
Output is correct |
8 |
Correct |
9 ms |
6656 KB |
Output is correct |
9 |
Correct |
10 ms |
6656 KB |
Output is correct |
10 |
Correct |
10 ms |
6784 KB |
Output is correct |
11 |
Correct |
9 ms |
6656 KB |
Output is correct |
12 |
Correct |
9 ms |
6656 KB |
Output is correct |
13 |
Correct |
9 ms |
6656 KB |
Output is correct |
14 |
Correct |
9 ms |
6656 KB |
Output is correct |
15 |
Correct |
9 ms |
6656 KB |
Output is correct |
16 |
Correct |
8 ms |
6656 KB |
Output is correct |
17 |
Correct |
9 ms |
6656 KB |
Output is correct |
18 |
Correct |
8 ms |
6656 KB |
Output is correct |
19 |
Correct |
9 ms |
6656 KB |
Output is correct |
20 |
Correct |
9 ms |
6656 KB |
Output is correct |
21 |
Correct |
9 ms |
6656 KB |
Output is correct |
22 |
Correct |
8 ms |
6656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
71 ms |
8704 KB |
Output is correct |
2 |
Correct |
70 ms |
8704 KB |
Output is correct |
3 |
Correct |
76 ms |
8832 KB |
Output is correct |
4 |
Correct |
112 ms |
14456 KB |
Output is correct |
5 |
Correct |
106 ms |
14360 KB |
Output is correct |
6 |
Correct |
691 ms |
14456 KB |
Output is correct |
7 |
Correct |
672 ms |
14072 KB |
Output is correct |
8 |
Correct |
662 ms |
13948 KB |
Output is correct |
9 |
Correct |
56 ms |
6912 KB |
Output is correct |
10 |
Correct |
53 ms |
6912 KB |
Output is correct |
11 |
Correct |
52 ms |
6912 KB |
Output is correct |
12 |
Correct |
106 ms |
14336 KB |
Output is correct |
13 |
Correct |
105 ms |
14456 KB |
Output is correct |
14 |
Correct |
105 ms |
14328 KB |
Output is correct |
15 |
Correct |
41 ms |
6904 KB |
Output is correct |
16 |
Correct |
47 ms |
6932 KB |
Output is correct |
17 |
Correct |
18 ms |
6784 KB |
Output is correct |
18 |
Correct |
15 ms |
6784 KB |
Output is correct |
19 |
Correct |
12 ms |
6656 KB |
Output is correct |
20 |
Correct |
11 ms |
6656 KB |
Output is correct |
21 |
Correct |
10 ms |
6656 KB |
Output is correct |
22 |
Correct |
10 ms |
6656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2271 ms |
15224 KB |
Output is correct |
2 |
Correct |
2192 ms |
15236 KB |
Output is correct |
3 |
Execution timed out |
2531 ms |
25036 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |