제출 #1148500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148500		MuhammadSaram	Team Coding (EGOI24_teamcoding)	C++20	50 / 100	4097 ms	48328 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

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

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

void init(int u)
{
	st[u]=t++;
	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 dfs1(int u)
{
	if (nei[u].empty())
	{
		ans.push_back({1,0});
		dd[u][dep[u]]++;
		return;
	}
	int mx=nei[u][0];
	for (int i:nei[u])
	{
		if (subt[i]>subt[mx])
			mx=i;
		dfs1(i);
	}
	swap(dd[u],dd[mx]);
	dd[u][dep[u]]++;
	for (int i:nei[u])
	{
		if (i!=mx)
			for (auto [d,c]:dd[i])
				dd[u][d]+=c;
	}
	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]])
	{
		if (dd[u].find(w)!=dd[u].end())
			x+=min(dd[u][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)
	{
		sp.clear(),gl=0;
		dfs2(u,l);
		int x=0;
		for (auto [w,h]:sp)
		{
			if (cnt[l].find(w)!=cnt[l].end())
				x+=min(cnt[l][w],h);
		}
		ans.push_back({x,x-gl});
	}
	for (int i:nei[u])
		dfs(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;
		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