제출 #1148351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148351		Faisal_Saqib	Team Coding (EGOI24_teamcoding)	C++20	62 / 100	4093 ms	43092 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];
set<int> occur[N];
pair<int,int> min_ans={0,0};
void dfs_sz(int x,int p=-1)
{
  tree[h[x]][color[x]]++;
  sz[x]=1;
  occur[color[x]].insert(h[x]);
  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;
  // cout<<"NODe "<<x<<" caioo asL ";
  // for(int h=1;h<=n;h++) // either iterate over all height where their is atleast one of color[x]s
  for(int h:occur[color[x]]) // either iterate over all height where their is atleast one of color[x]s
  {
  	ans_p+=subtree[h][color[x]];
  	// cout<<subtree[h][color[x]]<<' '<<h<<endl;
  	step_p+=min(cnt[h]-subtree[h][color[x]],tree[h][color[x]]-subtree[h][color[x]]);
  	if(min(cnt[h]-subtree[h][color[x]],tree[h][color[x]]-subtree[h][color[x]])<0)cout<<"Error"<<endl;
  }
  // cout<<endl;
  // if((ans_p+step_p)>4)
  // {
  	// cout<<"Node "<<x<<' '<<-ans_p-step_p<<' '<<step_p<<endl;
  // }
  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];
bool subtask=1;
  for(int i=1;i<n;i++)
  {
    int x=i,y;
    cin>>y;
    subtask&=(y==(x-1));
    // cout<<y<<' '<<x<<endl;
    ma[y].push_back(x);
  }
  if(subtask)
  {
  	map<int,int> apt;
  	int mx=0;
  	for(int i=n-1;i>=0;i--)
  		mx=max(mx,++apt[color[i]]);
  	cout<<mx<<' '<<0<<endl;
	return 0;
  }
  h[0]=1;
  dfs_sz(0);
  dfs(0);
  cout<<-min_ans.first<<' '<<min_ans.second<<endl;
}

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