Submission #1148436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148436		KaleemRazaSyed	Team Coding (EGOI24_teamcoding)	C++20	81 / 100	4090 ms	44616 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, S = 350;
int n, k, a[N], ans, mi, occur[N], C[N], h[N];
vector<int> child[N];
set<int> vec[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)
{
  vec[a[v]].insert(h[v]);
  cnt[a[v]][h[v]] ++;
  for(int c : child[v])
    {
      h[c] = h[v] + 1;
      prejob(c);
    }
}

int cc[N];
int col[N];
void dfs2(int v)
{
  vector<int> sz;
  int X = cc[a[v]];
  if(col[a[v]] == 0)
    {
      for(int hv : vec[a[v]])
	if(hv >= h[v])
	  sz.push_back(C[hv]);
    }
  
  col[a[v]] ++;

  cc[a[v]]++;
  C[h[v]]++;
  
  for(int c : child[v])
    dfs2(c);

  col[a[v]]--;
  X = cc[a[v]] - X;
  if(col[a[v]] == 0)
    {
      int i = 0;
      int sol = 0;
      for(int hv : vec[a[v]])
	if(hv >= h[v])
	  {
	    sol += min(C[hv] - sz[i], cnt[a[v]][hv]);
	    i++;
	  }
      if(sol > ans)
	ans = sol, mi = sol - X;
      else if(sol == ans)
	mi = min(mi, sol - X);	
    }
  
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  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 ++)
    if(occur[i] >= S)
      dfs(0, i);

  if(ans < S)
    dfs2(0);

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

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