Submission #1266573

#TimeUsernameProblemLanguageResultExecution timeMemory
1266573codergTeam Coding (EGOI24_teamcoding)C++20
62 / 100
4096 ms65744 KiB
#include <bits/stdc++.h> #include <cstdio> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); 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 prv_c = par[c[i]]; if (prv_c == -1) { is_root[i] = true; } else { col_adj[prv_c].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]] = prv_c; }; 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>> counts(n); map<int, int> curr_col; int ans1 = 0, ans2 = 0; const int M = sqrt(n); auto dfs1 = [&](auto& dfs1, int i) -> void { counts[i][depth[i]]++; for (auto& u : adj[i]) { dfs1(dfs1, u); if (counts[i].size() < counts[u].size()) swap(counts[i], counts[u]); for (auto& [d, cnt] : counts[u]) { counts[i][d] += cnt; } counts[u].clear(); } curr_col.clear(); if (is_root[i]) { queue<int> q; q.push(i); while (q.size()) { int v = q.front(); q.pop(); curr_col[depth[v]]++; 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 (counts[i].count(d)) { int space = counts[i][d]; int get = min(space, col_cnt[color][d]); now1 += get; now2 += 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]++; 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] && tot[c[i]] > M) { 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 get = min(cnt[d], col_cnt[c[i]][true_d]); now1 += get; now2 += 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...