Submission #1148371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148371		Faisal_Saqib	Team Coding (EGOI24_teamcoding)	C++20	12 / 100	38 ms	23368 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> maintain_ans[10];
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;
// ans_p+=subtree[h][color[x]];
// step_p+=min(cnt[h]-subtree[h][color[x]],tree[h][color[x]]-subtree[h][color[x]]);
void rem_contro(int he,int co)
{
	maintain_ans[co].first-=subtree[he][co];
	maintain_ans[co].second-=min(cnt[he]-subtree[he][co],tree[he][co]-subtree[he][co]);
}
void add_contro(int he,int co)
{
	maintain_ans[co].first+=subtree[he][co];
	maintain_ans[co].second+=min(cnt[he]-subtree[he][co],tree[he][co]-subtree[he][co]);
}

void adder(int x,int p)
{
	if(color[x]<=2)
	{
		rem_contro(h[x],color[x]);
	}

  cnt[h[x]]++;
  subtree[h[x]][color[x]]++;
	if(color[x]<=2)
	{
		add_contro(h[x],color[x]);
	}
  for(auto y:ma[x])
  {
    if(y==p)continue;
    adder(y,x);
  }
}


void deleter(int x,int p)
{
	if(color[x]<=2)
	{
		rem_contro(h[x],color[x]);
	}
  cnt[h[x]]--;
  subtree[h[x]][color[x]]--;
	if(color[x]<=2)
	{
		add_contro(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;
  maintain_ans[0]=maintain_ans[1]={0,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]]);
  	if(color[x]<=2)
	{
		rem_contro(h[x],color[x]);
	}
  cnt[h[x]]++;
  subtree[h[x]][color[x]]++;
	if(color[x]<=2)
	{
		add_contro(h[x],color[x]);
		min_ans=min(min_ans,{-maintain_ans[color[x]].first-maintain_ans[color[x]].second,maintain_ans[color[x]].second});
		// min_ans=min(min_ans,{-maintain_ans[0].first-maintain_ans[0].second,maintain_ans[0].second});
		// min_ans=min(min_ans,{-maintain_ans[1].first-maintain_ans[1].second,maintain_ans[1].second});
	}
	else
	{
	  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;
	  }
	  min_ans=min(min_ans,{-ans_p-step_p,step_p});
	}
  // cout<<endl;
  // if((ans_p+step_p)>4)
  // {
  	// cout<<"Node "<<x<<' '<<-ans_p-step_p<<' '<<step_p<<endl;
  // }




  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=0;i<5;i++)
  {
  	maintain_ans[i]={0,0};
  }
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: 0 / 27
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19