Submission #1148564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148564		MuhammadSaram	Team Coding (EGOI24_teamcoding)	C++20	50 / 100	4094 ms	36164 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

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

vector<int> nei[M],pr[M];
unordered_map<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];
int f1,f2;

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())
	{
		if (!f1) f1=1;
		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);
	if (f1<x)
		f1=x,f2=x-y;
	if (f1==x)
		f2=(f2<x-y?f2: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]);
		if (f1<x)
			f1=x,f2=x-gl;
		if (f1==x)
			f2=(f2<x-gl?f2: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);
	}
	int r=0;
	init(0);
	dfs1(r);
	for (int l=0;l<k;l++)
	{
		if (pr[l].size()<=sq) continue;
		for (int i=0;i<n;i++) cnt1[i]=0;
		dfs3(r,l);
		dfs(r,l);
	}
	cout<<f1<<' '<<f2<<endl;
	
	return 0;
}

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