Submission #1148322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148322		Faisal_Saqib	Team Coding (EGOI24_teamcoding)	C++20	23 / 100	4096 ms	1114112 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;
vector<int> ma[N];
int h[N],sz[N],cnt[N],ans=0,color[N],cur_ans=0,n,k;
map<int,int> subtree[N],tree[N];
pair<int,int> min_ans={0,0};
void dfs_sz(int x,int p=-1)
{
  tree[h[x]][color[x]]++;
  sz[x]=1;
  for(auto y:ma[x])
  {
    if(y==p)continue;
    h[y]=h[x]+1;
    dfs_sz(y,x);
    sz[x]+=sz[y];
  }
}
int req_color;
void adder(int x,int p)
{
  cnt[h[x]]++;
  subtree[h[x]][color[x]]++;
  for(auto y:ma[x])
  {
    if(y==p)continue;
    adder(y,x);
  }
}


void deleter(int x,int p)
{
  cnt[h[x]]--;
  subtree[h[x]][color[x]]--;
  for(auto y:ma[x])
  {
    if(y==p)continue;
    deleter(y,x);
  }
}


void dfs(int x,int p=-1,bool keep=0)
{
  int big=-1;
  for(auto y:ma[x])
  {
    if(y==p)continue;
    if(big==-1 or sz[big]<sz[y])
      big=y;
  }
  for(auto y:ma[x])
  {
    if(y==p or y==big)continue;
    dfs(y,x);
  }
  // cur_ans=0;
  if(big!=-1)
  {
    dfs(big,x,1);
  }
  for(auto y:ma[x])
  {
    if(y==p or y==big)continue;
    adder(y,x);    
  }
  

  //Real solving part is this
  // cnt[color[x]]++;
  // ans=max(ans,cnt[color[x]]);
  cnt[h[x]]++;
  subtree[h[x]][color[x]]++;
  int ans_p=0,step_p=0;
  for(int h=1;h<=n;h++) // either iterate over all height where their is atleast one of color[x]s
  {
  	ans_p+=subtree[h][color[x]];
  	step_p+=min(cnt[h]-subtree[h][color[x]],tree[h][color[x]]-subtree[h][color[x]]);
  }
  min_ans=min(min_ans,{-ans_p-step_p,step_p});




  if(!keep)
  {
    deleter(x,p);
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>k;
  for(int i=0;i<n;i++)cin>>color[i];
  for(int i=1;i<n;i++)
  {
    int x=i,y;
    cin>>y;
    ma[y].push_back(x);
  }
  h[0]=1;
  dfs_sz(0);
  dfs(0);
  cout<<-min_ans.first<<' '<<min_ans.second<<endl;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 19
• Subtask 3: 0 / 27
• Subtask 4: 23 / 23
• Subtask 5: 0 / 19