#include <cstdio>
#include <vector>
using namespace std;
template<class T> using V = vector<T>;
struct Node {
using NP = Node*;
NP l, r; int sz;
Node(int sz, int f[]) : sz(sz) {
if (sz == 1) {
ma = f[0];
return;
}
l = new Node(sz/2, f);
r = new Node(sz-sz/2, f+sz/2);
ma = max(l->ma, r->ma);
}
int ma;
void set(int k, int x) {
if (sz == 1) {
ma = x;
return;
}
if (k < sz/2) {
l->set(k, x);
} else {
r->set(k-sz/2, x);
}
ma = max(l->ma, r->ma);
}
int sea(int b, int x) {
if (b <= 0 || ma < x) return -1;
if (sz == 1) return 0;
int u = r->sea(b - sz/2, x);
if (u != -1) return u + sz/2;
return l->sea(b, x);
}
};
const int MN = 100100;
V<int> g[MN];
int lc, rc;
int dps[MN], lid[MN], rid[MN], lrev[MN];
void dfs(int p, int b, int dp = 0) {
dps[p] = dp;
lrev[lc] = p;
lid[p] = lc++;
for (int d: g[p]) {
if (d == b) continue;
dfs(d, p, dp+1);
}
rid[p] = rc++;
}
int vc[MN], uc[MN];
int e_x[MN], e_y[MN], e_on[MN];
int main() {
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
fill(vc, vc+n, 1);
for (int i = 0; i < n-1; i++) {
scanf("%d %d", e_x+i, e_y+i); e_x[i]--; e_y[i]--;
g[e_x[i]].push_back(e_y[i]);
g[e_y[i]].push_back(e_x[i]);
}
dfs(0, -1);
Node* rmq = new Node(n, rid);
auto rt = [&](int p) {
return lrev[rmq->sea(lid[p]+1, rid[p])];
};
auto ad = [&](int p) {
rmq->set(lid[p], rid[p]);
};
auto er = [&](int p) {
rmq->set(lid[p], -1);
};
for (int i = 0; i < m; i++) {
int e;
scanf("%d", &e); e--;
int x = e_x[e], y = e_y[e];
if (dps[x] < dps[y]) swap(x, y);
if (!e_on[e]) {
//inc
vc[rt(y)] += vc[x] - uc[x];
er(x);
} else {
//dec
vc[x] = uc[x] = vc[rt(y)];
ad(x);
}
e_on[e] = 1-e_on[e];
}
for (int i = 0; i < q; i++) {
int x;
scanf("%d", &x); x--;
printf("%d\n", vc[rt(x)]);
}
return 0;
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:65:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &q);
^
synchronization.cpp:68:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", e_x+i, e_y+i); e_x[i]--; e_y[i]--;
^
synchronization.cpp:85:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &e); e--;
^
synchronization.cpp:102:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x); x--;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
7056 KB |
Output is correct |
2 |
Correct |
0 ms |
7056 KB |
Output is correct |
3 |
Correct |
0 ms |
7056 KB |
Output is correct |
4 |
Correct |
0 ms |
7056 KB |
Output is correct |
5 |
Incorrect |
0 ms |
7056 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
159 ms |
19704 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
7056 KB |
Output is correct |
2 |
Correct |
0 ms |
7056 KB |
Output is correct |
3 |
Correct |
0 ms |
7056 KB |
Output is correct |
4 |
Correct |
0 ms |
7056 KB |
Output is correct |
5 |
Correct |
0 ms |
7056 KB |
Output is correct |
6 |
Correct |
0 ms |
7188 KB |
Output is correct |
7 |
Correct |
19 ms |
8484 KB |
Output is correct |
8 |
Correct |
369 ms |
22552 KB |
Output is correct |
9 |
Correct |
373 ms |
22552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
363 ms |
22556 KB |
Output is correct |
2 |
Correct |
149 ms |
22508 KB |
Output is correct |
3 |
Correct |
139 ms |
22548 KB |
Output is correct |
4 |
Correct |
139 ms |
22552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
7056 KB |
Output is correct |
2 |
Incorrect |
0 ms |
7056 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |