# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1187883 | _ncng.nyr | Synchronization (JOI13_synchronization) | C++20 | 8095 ms | 15688 KiB |
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, k, timer;
int in[N], out[N], rev[N], state[N], ans[N], boss[N], par[N], pre[N];
pair<int, int> e[N];
vector<int> ad[N];
map<pair<int, int>, bool> del;
void dfs (int u, int p) {
in[u] = ++timer;
rev[timer] = u;
for (auto v : ad[u]) if (v != p) {
par[v] = u;
dfs(v, u);
}
out[u] = timer;
}
int root (int v) {
while (par[v] != v) v = par[v];
return v;
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(0);
#define task "Synchronization"
if (fopen ("task.inp", "r")) {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
}
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
cin >> n >> m >> k;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
ad[u].push_back(v);
ad[v].push_back(u);
e[i] = {u, v};
}
dfs(1, 0);
for (int i = 1; i < n; ++i) {
auto [u, v] = e[i];
if (in[u] > in[v]) swap(u, v);
e[i] = {u, v};
}
for (int i = 1; i <= n; ++i) ans[i] = 1, par[i] = i;
for (int i = 1; i <= m; ++i) {
int id; cin >> id;
state[id] ^= 1;
auto [u, v] = e[id];
if (state[id]) {
int head = root(u),
res = ans[head] + ans[v] - pre[id];
ans[head] = ans[v] = res;
par[v] = u;
}
else {
int head = root(u);
pre[id] = ans[head];
ans[v] = ans[head]; par[v] = v;
}
}
while (k--) {
int u; cin >> u;
cout << ans[u] << '\n';
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |