Submission #1187395

#TimeUsernameProblemLanguageResultExecution timeMemory
1187395mannshah1211Mergers (JOI19_mergers)C++20
0 / 100
50 ms26688 KiB
/** * author: tourist * created: 17.04.2025 15:40:37 **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif class dsu { public: vector<int> p; int n; dsu(int _n) : n(_n) { p.resize(n); iota(p.begin(), p.end(), 0); } int get(int x) { if (p[x] == x) { return x; } return p[x] = get(p[x]); } bool unite(int u, int v) { u = get(u); v = get(v); if (u != v) { p[v] = u; return true; } return false; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); g[v].push_back(u); } vector<int> s(n); vector<vector<int>> at(k); for (int i = 0; i < n; i++) { cin >> s[i]; --s[i]; at[s[i]].push_back(i); } vector<int> tin(n), tout(n); vector<vector<int>> pv(n, vector<int>(19)); int timer = 0; auto Dfs = [&](auto&& self, int v, int pr) -> void { tin[v] = timer++; pv[v][0] = pr; for (int u : g[v]) { if (u != pr) { self(self, u, v); } } tout[v] = timer; }; Dfs(Dfs, 0, -1); for (int j = 1; j < 19; j++) { for (int i = 0; i < n; i++) { if (pv[i][j - 1] == -1) { pv[i][j] = -1; } else { pv[i][j] = pv[pv[i][j - 1]][j - 1]; } } } auto Anc = [&](int u, int v) { return (tin[u] <= tin[v]) && (tout[v] <= tout[u]); }; auto lca = [&](int u, int v) { if (Anc(u, v)) { return u; } for (int b = 18; b >= 0; b--) { if (pv[u][b] != -1 && !Anc(pv[u][b], v)) { u = pv[u][b]; } } assert(pv[u][0] != -1); return pv[u][0]; }; vector<int> values(n); auto Add = [&](int u, int v) { if (Anc(u, v)) { values[u] += 1; values[v] -= 1; return; } if (Anc(v, u)) { values[v] += 1; values[u] -= 1; return; } int w = lca(u, v); values[w] += 1; values[u] -= 1; values[v] -= 1; }; for (int i = 0; i < k; i++) { sort(at[i].begin(), at[i].end(), [&](int u, int v) { return (tin[u] < tin[v]); }); for (int j = 0; j < static_cast<int>(at[i].size()) - 1; j++) { Add(at[i][j], at[i][j + 1]); } } int sum = 0; auto Accumulate = [&](auto&& self, int v, int pr) -> void { int original = values[v]; values[v] = sum; sum += original; for (int u : g[v]) { if (u != pr) { self(self, u, v); } } sum -= original; }; Accumulate(Accumulate, 0, -1); dsu ds(n); for (int v = 1; v < n; v++) { if (values[v] != 0) { ds.unite(v, pv[v][0]); } } vector<int> component_values; for (int v = 0; v < n; v++) { component_values.push_back(ds.get(v)); } vector<int> who(n, -1); int ptr = 0; for (int i = 0; i < n; i++) { if (who[component_values[i]] == -1) { who[component_values[i]] = ptr; ptr++; } } vector<int> deg(ptr); for (int v = 1; v < n; v++) { if (values[v] == 0) { ++deg[who[ds.get(pv[v][0])]]; ++deg[who[ds.get(v)]]; } } int leaves = 0; for (int i = 0; i < ptr; i++) { if (deg[i] == 1) { leaves++; } } cout << (leaves + 1) / 2 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...