Submission #1266570

#TimeUsernameProblemLanguageResultExecution timeMemory
1266570codergTeam Coding (EGOI24_teamcoding)C++20
0 / 100
0 ms328 KiB
/* 02.09.2025 */ #include <bits/stdc++.h> using namespace std; typedef long long ll; #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); signed main(){ fastIO; int n,k;cin>>n>>k; vector<int> c(n); vector<vector<int>> adj(n); vector<int> tot(k); for (int i = 0; i < n; ++i) { cin >> c[i]; tot[c[i]]++; } for (int i = 1; i < n; ++i) { int x;cin >> x; adj[x].push_back(i); } vector<bool> is_root(n); vector<vector<int>> col_adj(n); vector<int> depth(n), mx_depth(n); vector<unordered_map<int, int>> col_cnt(k); vector<vector<int>> diff_depths(k); auto dfs = [&](auto& dfs, int i, vector<int>& par) -> void { int v = par[c[i]]; if (v == -1) { is_root[i] = true; } else { col_adj[v].push_back(i); } par[c[i]] = i; mx_depth[i] = depth[i]; col_cnt[c[i]][depth[i]]++; diff_depths[c[i]].push_back(depth[i]); for (auto& u : adj[i]) { depth[u] = depth[i] + 1; dfs(dfs, u, par); mx_depth[i] = max(mx_depth[i], mx_depth[u]); } par[c[i]] = v; }; vector<int> par(k, -1); dfs(dfs, 0, par); for (int i = 0; i < k; ++i) { auto& v = diff_depths[i]; sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } vector<map<int, int>> cnts(n); map<int, int> curr_col; int ans1=0,ans2=0; const int M = sqrt(n); auto dfs1 = [&](auto& dfs1, int i) -> void { cnts[i][depth[i]] += 1; for (auto& u : adj[i]) { dfs1(dfs1, u); if (cnts[i].size() < cnts[u].size()) swap(cnts[i], cnts[u]); for (auto& [d, cnt] : cnts[u]) { cnts[i][d] += cnt; } cnts[u].clear(); } curr_col.clear(); if (is_root[i] && tot[c[i]] <= M) { queue<int> q; q.push(i); while (q.size()) { int v = q.front(); q.pop(); curr_col[depth[v]] += 1; for (auto& u : col_adj[v]) { q.push(u); } } int now1 = 0, now2 = 0; const int color = c[i]; for (auto& d : diff_depths[color]) { if (cnts[i].count(d)) { int space = cnts[i][d]; int can_get = min(space, col_cnt[color][d]); now1 += can_get; now2 += can_get - curr_col[d]; } } if (ans1 < now1) { ans1 = now1; ans2 = now2; } if (ans1 == now1) ans2 = min(ans2, now2); } }; dfs1(dfs1, 0); cout<< ans1<<" "<<ans2<<'\n'; return 0; vector<vector<int>> roots(k); auto dfs2 = [&](auto& dfs2, int i, vector<int>& cnt, vector<int>& cur_col_cnt, int d, const int need) -> void { while (d >= (int)cnt.size()) cnt.push_back(0); while (d >= (int)cur_col_cnt.size()) cur_col_cnt.push_back(0); cnt[d] += 1; if (c[i] == need) cur_col_cnt[d]++; for (auto& u : adj[i]) { dfs2(dfs2, u, cnt, cur_col_cnt, d + 1, need); } }; for (int i = 0; i < n; ++i) { if (is_root[i]) { vector<int> cnt, cur_col_cnt; dfs2(dfs2, i, cnt, cur_col_cnt, 0, c[i]); cnt.push_back(0); int d = 0; int now1 = 0, now2 = 0; while (cnt[d] > 0) { int true_d = d + depth[i]; if (col_cnt[c[i]].count(true_d)) { int can_get = min(cnt[d], col_cnt[c[i]][true_d]); now1 += can_get; now2 += can_get-cur_col_cnt[d]; } d++; } if (ans1<now1) { ans1=now1; ans2=now2; } if (ans1==now1) ans2 = min(ans2,now2); } } cout<<ans1<<" "<<ans2<<"\n"; }
#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...