Submission #1266577

#TimeUsernameProblemLanguageResultExecution timeMemory
1266577codergTeam Coding (EGOI24_teamcoding)C++20
19 / 100
81 ms51552 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]]+=1; } 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> current_col; int ans1=0,ans2=0; const int M=sqrt(n); auto dfs1=[&](auto& dfs1,int i)->void { cnts[i][depth[i]]++; 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(); } current_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(); current_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 (cnts[i].count(d)) { int space=cnts[i][d]; int get=min(space, col_cnt[color][d]); now1 =get; now2+=get-current_col[d]; } } if (ans1<now1) { ans1=now1; ans2=now2; } if (ans1==now1) ans2=min(ans2,now2); } }; dfs1(dfs1,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]+=1; 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+=1; } if (ans1<now1) { ans1=now1; ans2=now2; } if (ans1==now1) ans2=min(ans2,now2); } } cout<<ans1<<' '<<ans2<<'\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...