Submission #1148369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148369		KaleemRazaSyed	Team Coding (EGOI24_teamcoding)	C++20	42 / 100	3135 ms	1114112 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, k, a[N], ans, mi, occur[N], C[N], h[N];
vector<int> child[N];
map<int, int> cnt[N];

void bfs(int v)
{
  queue<int> Q;
  Q.push(v);
  int X = 0;
  while(Q.size())
    {
      int u = Q.front();
      Q.pop();
      X += (a[v] == a[u]);
      C[h[u]]++;
      for(int c : child[u])
	Q.push(c);
    }

  int sol = 0;
  for(int i = h[v]; C[i] > 0; i++)
    {
      sol += min(C[i], cnt[a[v]][i]);
      C[i] = 0;
    }

  if(sol > ans)
    ans = sol, mi = sol - X;
  else if(sol == ans)
    mi = min(sol - X, mi);

  
}

void dfs(int v, int color)
{
  if(a[v] == color)
    {
      bfs(v);
      return;
    }
  
  for(int c : child[v])
    dfs(c, color);
}

void prejob(int v)
{
  cnt[a[v]][h[v]] ++;
  for(int c : child[v])
    {
      h[c] = h[v] + 1;
      prejob(c);
    }
}

int main()
{
  cin >> n >> k;
  for(int i = 0; i < n; i ++)
    {
      cin >> a[i];
      occur[a[i]]++;
    }

  cnt[a[0]][0]++;
  for(int i = 1; i < n; i ++)
    {
      int p;
      cin >> p;
      child[p].push_back(i);
    }

  prejob(0);

  for(int i = 0; i < k; i ++)
    dfs(0, i);

  cout << ans << ' ' << mi << endl;  
  return 0;
}

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