#include "bits/stdc++.h"
using namespace std;
int l[100010], r[100010];
int n;
int par[100010];
vector <int> g[100010];
int sub[100010];
bool del[100010];
int rt[100010];
bool vis[100010];
int sz[100010];
int last[100010];
vector <int> aux[100010];
void dfs(int x, int p) {
sub[x] = 1;
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(e != p && !del[i]) {
dfs(i, e);
sub[x] += sub[i];
}
}
}
int centroid(int x, int p, int range) {
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(e != p && sub[i] > range && !del[i]) {
return centroid(i, e, range);
}
}
return x;
}
vector <int> nodes;
void prec(int x, int p, int src) {
par[x] = p;
rt[x] = src;
nodes.push_back(x);
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(e != p && !del[i]) {
prec(i, e, src);
}
}
}
int root(int u) {
while(vis[par[u]]) {
u ^= l[par[u]] ^ r[par[u]];
}
return u;
}
struct data {
int r, cnt, pos;
data (int r, int cnt, int pos) : r(r), cnt(cnt), pos(pos) {}
data () {}
bool operator < (data f) const {
return pos < f.pos;
}
};
bool cmp(int i, int j) {
return last[i] < last[j];
}
int ans[100010];
int sum[100010];
void solve(int x, vector <int> &Q) {
dfs(x, 0);
x = centroid(x, 0, sub[x] / 2);
del[x] = true;
nodes.clear();
par[x] = 0;
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(del[i]) continue;
prec(i, e, i);
sum[i] = 0;
aux[i].clear();
}
for(auto i : nodes) {
vis[par[i]] = 0;
sz[i] = 1;
}
vector <data> cont;
sum[x] = 0;
cont.emplace_back(x, 1, -1);
for(int h = 0; h < Q.size(); h++) {
int e = Q[h];
int u;
if(par[l[e]] == e) u = l[e];
else u = r[e];
if(!vis[e]) {
vis[e] ^= 1;
if(root(u) == x) {
if (sz[u] > 0) {
cont.emplace_back(rt[u], sz[u], h);
}
sz[u] = 0;
} else {
sz[root(u)] += sz[u];
sz[u] = 0;
}
} else {
vis[e] ^= 1;
}
}
sort(cont.begin(), cont.end());
for(auto i : cont) {
ans[x] += i.cnt;
}
for(auto i : nodes) {
vis[par[i]] = 0;
last[i] = INT_MIN;
}
for(int h = 0; h < Q.size(); h++) {
int e = Q[h];
int u;
if(par[l[e]] == e) u = l[e];
else u = r[e];
last[x] = h;
if(vis[e]) {
last[u] = last[root(u)];
vis[e] ^= 1;
} else {
vis[e] ^= 1;
}
}
last[x] = Q.size();
for(auto i : nodes) {
last[i] = last[root(i)];
}
sort(nodes.begin(), nodes.end(), cmp);
int pt = 0;
int tot = 0;
for(int i : nodes) {
while(pt < cont.size() && cont[pt].pos < last[i]) {
sum[cont[pt].r] += cont[pt].cnt;
tot += cont[pt].cnt;
++pt;
}
ans[i] += tot - sum[rt[i]];
}
for(int h = 0; h < Q.size(); h++) {
int e = Q[h];
int u;
if(par[l[e]] == e) u = l[e];
else u = r[e];
if(rt[u] != u) {
aux[rt[u]].push_back(e);
}
}
for(auto e : g[x]) {
int i = l[e] ^ r[e] ^ x;
if(del[i]) continue;
solve(i, aux[i]);
}
}
int main(int argc, char const *argv[])
{
int m, qr;
scanf("%d %d %d", &n, &m, &qr);
for(int i = 1; i < n; i++) {
scanf("%d %d", l + i, r + i);
g[l[i]].push_back(i);
g[r[i]].push_back(i);
}
vector <int> Q;
for(int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
Q.push_back(x);
}
solve(1, Q);
for(int i = 1; i <= qr; i++) {
int u;
scanf("%d", &u);
printf("%d\n", ans[u]);
}
return 0;
}
Compilation message
synchronization.cpp: In function 'void solve(int, std::vector<int>&)':
synchronization.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < Q.size(); h++) {
~~^~~~~~~~~~
synchronization.cpp:122:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < Q.size(); h++) {
~~^~~~~~~~~~
synchronization.cpp:145:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pt < cont.size() && cont[pt].pos < last[i]) {
~~~^~~~~~~~~~~~~
synchronization.cpp:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < Q.size(); h++) {
~~^~~~~~~~~~
synchronization.cpp: In function 'int main(int, const char**)':
synchronization.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &qr);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", l + i, r + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:182:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
synchronization.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &u);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5092 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5156 KB |
Output is correct |
| 7 |
Incorrect |
25 ms |
6264 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8061 ms |
16988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
34652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
