Submission #1148352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148352		MuhammadSaram	Team Coding (EGOI24_teamcoding)	C++20	50 / 100	4093 ms	21572 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

const int M = 1e5 + 1;

vector<int> nei[M],ver[M];
int dep[M],st[M],en[M],t;

void dfs(int u)
{
	st[u]=t++;
	ver[dep[u]].push_back(st[u]);
	for (int i:nei[u])
		dep[i]=dep[u]+1,dfs(i);
	en[u]=t++;
}

int main()
{
	int n,k;
	cin>>n>>k;
	vector<int> v[k];
	for (int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		v[x].push_back(i);
	}
	for (int i=1;i<n;i++)
	{
		int p;
		cin>>p;
		nei[p].push_back(i);
	}
	dfs(0);
	int ans=0,s=0;
	for (int l=0;l<k;l++)
	{
		for (int u:v[l])
		{
			map<int,int> cnt,tot;
			int x=1,y=0;
			for (int j:v[l])
			{
				if (dep[j]<=dep[u]) continue;
				if (tot.find(dep[j])==tot.end())
					tot[dep[j]]=lower_bound(all(ver[dep[j]]),en[u])-lower_bound(all(ver[dep[j]]),st[u]);
				if (st[j]>st[u] && st[j]<en[u])
					x++,tot[dep[j]]--;
				else
					cnt[dep[j]]++;
			}
			for (auto [d,c]:cnt)
				x+=min(c,tot[d]),y+=min(c,tot[d]);
			if (x>ans)
				ans=x,s=y;
			else if(x==ans)
				s=min(s,y);
		}
	}
	cout<<ans<<' '<<s<<endl;
	
	return 0;
}

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