Submission #1172633

#TimeUsernameProblemLanguageResultExecution timeMemory
1172633ezzzayTeam Coding (EGOI24_teamcoding)C++20
0 / 100
406 ms845992 KiB
#include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back const int N=3e3; vector<int>v[N]; int lvl[N]; int col[N]; int cnt[N][N]; int par[N]; vector<pair<int,int>>vc[N]; pair<int,int>ans; map<int,int>mp[N][N]; map<int,int>pm[N][N]; void df(int a ){ cnt[lvl[a]][col[a]]++; for(auto b:v[a]){ lvl[b]=lvl[a]+1; df(b); } } int n,k; void dfs(int a ){ int h=0; vc[a].pb({lvl[a],col[a]}); int c=col[a]; for(auto b:v[a]){ dfs(b); if(vc[b].size()>vc[a].size()){ swap(vc[b],vc[a]); swap(mp[b][c],mp[a][c]); swap(pm[b][c],pm[a][c]); } for(auto it=mp[b][c].begin();it!=mp[b][c].end();it++){ mp[a][c][it->ff]+=it->ss; } for(auto it=pm[b][c].begin();it!=pm[b][c].end();it++){ pm[a][c][it->ff]+=it->ss; } for(auto p:vc[b]){ vc[a].pb(p); h=max(h,p.ff); } } mp[a][c][lvl[a]]++; for(int i=0;i<k;i++){ if(i!=c)pm[a][i][lvl[a]]++; } pair<int,int>t={1,0}; for(int i=lvl[a]+1; i<=h;i++){ t.ff+=mp[a][c][i]; t.ff+= min(pm[a][c][i],(cnt[i][c]-mp[a][c][i])); t.ss -= min(pm[a][c][i],(cnt[i][c]-mp[a][c][i])); } ans=max(ans,t); } signed main(){ cin>>n>>k; int mx=0; for(int i=0;i<n;i++){ cin>>col[i]; } for(int i=1;i<n;i++){ cin>>par[i]; v[par[i]].pb(i); } df(0); dfs(0); cout<<ans.ff<<" "<<-ans.ss<<endl; }
#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...