Submission #1172621

#TimeUsernameProblemLanguageResultExecution timeMemory
1172621ezzzayTeam Coding (EGOI24_teamcoding)C++20
23 / 100
750 ms30556 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; void df(int a ){ cnt[lvl[a]][col[a]]++; for(auto b:v[a]){ lvl[b]=lvl[a]+1; df(b); } } void dfs(int a ){ vc[a].pb({lvl[a],col[a]}); for(auto b:v[a]){ dfs(b); if(v[b].size()>v[a].size()){ swap(v[b],v[a]); } for(auto p:vc[b])vc[a].pb(p); } map<int,int>mp,pm; int h=0; for(auto p:vc[a]){ h=max(h,p.ff); if(p.ss==col[a]){ mp[p.ff]++; } else{ pm[p.ff]++; } } pair<int,int>t={1,0}; int c=col[a]; for(int i=lvl[a]+1; i<=h;i++){ t.ff+=mp[i]; t.ff+= min(pm[i],(cnt[i][c]-mp[i])); t.ss -= min(pm[i],(cnt[i][c]-mp[i])); } ans=max(ans,t); } signed main(){ int n,k; 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...