Submission #1148551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148551		MuhammadSaram	Team Coding (EGOI24_teamcoding)	C++20	50 / 100	4086 ms	45076 KiB

Main

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define all(v) v.begin(), v.end()

const int M = 1e5 + 1, sq = 750;

vector<int> nei[M],pr[M];
gp_hash_table<int,int> cnt[M];
int dep[M],a[M],mxd[M],subt[M],st[M],en[M],sp[M],t,gl,cnt1[M],dd[M];
vector<pair<int,int>> ans;

void init(int u)
{
	st[u]=t++;
	if (pr[a[u]].size()<=sq)
		cnt[a[u]][dep[u]]++;
	mxd[u]=dep[u],subt[u]=1;
	for(int i:nei[u])
	{
		dep[i]=dep[u]+1;
		init(i);
		mxd[u]=max(mxd[i],mxd[u]);
		subt[u]+=subt[i];
	}
	en[u]=t++;
}

void cll(int u,int x)
{
	dd[dep[u]]+=x;
	for (int i:nei[u])
		cll(i,x);
}

void dfs1(int u)
{
	if (nei[u].empty())
	{
		ans.push_back({1,0});
		dd[dep[u]]++;
		return;
	}
	int mx=nei[u][0];
	for (int i:nei[u])
	{
		if (subt[i]>subt[mx])
			mx=i;
	}
	for (int i:nei[u])
	{
		if (i!=mx)
		{
			dfs1(i);
			cll(i,-1);
		}
	}
	dfs1(mx);
	dd[dep[u]]++;
	for (int i:nei[u])
		if (i!=mx) cll(i,1);
	if (pr[a[u]].size()>sq) return;
	int x=0,y=0;
	for (int i:pr[a[u]])
		y+=(st[i]>=st[u] && st[i]<en[u]);
	for (auto [w,h]:cnt[a[u]])
		x+=min(dd[w],h);
	ans.push_back({x,x-y});
}

void dfs2(int u,int l)
{
	if (a[u]==l) gl++;
	sp[dep[u]]++;
	for (int i:nei[u])
		dfs2(i,l);
}

void dfs(int u,int l)
{
	if (a[u]==l)
	{
		gl=0;
		for (int w=dep[u];w<=mxd[u];w++) sp[w]=0;
		dfs2(u,l);
		int x=0;
		for (int w=dep[u];w<=mxd[u];w++)
			x+=min(cnt1[w],sp[w]);
		ans.push_back({x,x-gl});
	}
	for (int i:nei[u])
		dfs(i,l);
}

void dfs3(int u,int l)
{
	if (a[u]==l) cnt1[dep[u]]++;
	for (int i:nei[u]) dfs3(i,l);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	int n,k;
	cin>>n>>k;
	for (int i=0;i<n;i++)
		cin>>a[i],pr[a[i]].push_back(i);
	for (int i=1;i<n;i++)
	{
		int p;
		cin>>p;
		nei[p].push_back(i);
	}
	init(0);
	dfs1(0);
	for (int l=0;l<k;l++)
	{
		if (pr[l].size()<=sq) continue;
		for (int i=0;i<n;i++) cnt1[i]=0;
		dfs3(0,l);
		dfs(0,l);
	}
	int x=0,y=0;
	for (auto [p1,p2]:ans)
	{
		if (x<p1)
			x=p1,y=p2;
		if (x==p1)
			y=min(y,p2);
	}
	cout<<x<<' '<<y<<endl;
	
	return 0;
}

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