| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 343810 | hugo_pm | Synchronization (JOI13_synchronization) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "hl/core.hpp"
#include "hl/data/usual.hpp"
int main() {
int nb_node = nxt(), nb_switch = nxt(), nb_query = nxt();
Vec<2, int> adj(nb_node, 0);
vector<pair<int, int>> orig;
rep(id_edge, 0, nb_node - 1) {
int u = nxt() - 1, v = nxt() - 1;
adj[u].push_back(v);
adj[v].push_back(u);
orig.emplace_back(u, v);
}
const int ROOT = 0;
int nb_level = __lg(nb_node) + 1;
Vec<2, int> anc(nb_node, nb_level, -1);
vector<int> tin(nb_node), tout(nb_node);
int timer = 0;
auto build = letrec([&] (auto self, int node) -> void {
tin[node] = timer++;
rep(l, 1, nb_level) {
int t = anc[node][l-1];
if (t == -1) break;
anc[node][l] = anc[t][l-1];
}
for (int child : adj[node]) if (child != anc[node][0]) {
anc[child][0] = node;
self(child);
}
tout[node] = timer++;
});
build(ROOT);
vector<bool> active(nb_node, false);
sum32::st rsum(timer+1, 0);
auto find_root = [&] (int node) {
for (int level = nb_level-1; level >= 0; --level) {
int jto = anc[node][level];
if (jto == -1) continue;
int nb_active = rsum.query_semi_open(tin[jto], tin[node] + 1) - active[jto];
if (nb_active == (1 << (level+1)) - 1) {
node = jto;
}
}
return node;
};
auto upd = [&] (int node, int x) {
rsum.set(tin[node], x);
rsum.set(tout[node], -x);
active[node] = x;
};
vector<int> info(nb_node, 1), last_sync(nb_node, 0);
rep(id_switch, 0, nb_switch) {
auto [par, low] = orig[nxt()-1];
if (low == anc[par][0]) swap(par, low);
if (active[low]) {
info[low] = last_sync[low] = info[find_root(low)];
upd(low, 0);
} else {
upd(low, 1);
info[find_root(low)] += info[low] - last_sync[low];
}
}
rep(id_query, 0, nb_query) {
int u = nxt() - 1;
cout << info[find_root(u)] << "\n";
}
}