Submission #1148261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148261		Faisal_Saqib	Team Coding (EGOI24_teamcoding)	C++20	12 / 100	41 ms	36420 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;
vector<int> ma[N];
int h[N],sz[N],cnt[N],ans=0,color[N];

void dfs_sz(int x,int p=-1)
{
  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];
  }
}
void adder(int x,int p)
{
  cnt[color[x]]++;
  for(auto y:ma[x])
  {
    if(y==p)continue;
    adder(y,x);
  }
}


void deleter(int x,int p)
{
  cnt[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);
  }
  if(big!=-1)
  {
    dfs(big,x,1);
  }
  for(auto y:ma[x])
  {
    if(y==p or y==big)continue;
    adder(y,x);    
  }
  cnt[color[x]]++;
  ans=max(ans,cnt[color[x]]);
  if(!keep)
  {
    deleter(x,p);
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,k;
  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[x].push_back(y);
    ma[y].push_back(x);
  }
  h[0]=1;
  dfs_sz(0);
  dfs(0);
  cout<<ans<<' '<<0<<endl;
}

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