Submission #1249149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249149		arashmemar	Capital City (JOI20_capital_city)	C++20	1 / 100	198 ms	41024 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100;

bool mark[maxn];
vector <int> poec[maxn], ne[maxn];
int p[maxn], c[maxn];
bool s[maxn];
int nos[maxn], vu[maxn];

int find(int v, int k)
{
	nos[c[v]] = 0;
	s[c[v]] = 0;
	mark[v] = 1;
	bool ok = 1;
	vu[v] = 1;
	int ret = -1;
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		p[u] = v;
		ret = max(ret, find(u, k));
		vu[v] += vu[u];
		ok &= (vu[u] <= k / 2);
	}
	if (ok and vu[v] >= (k + 1) / 2)
	{
		ret = v;
	}
	mark[v] = 0;
	return ret;
}

void dfs(int v, bool op)
{
	mark[v] = 1;
	if (s[c[v]] == 0 and op)
	{
		nos[c[v]]++;
	}
	s[c[v]] = op;
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		dfs(u, op);
	}
	mark[v] = 0;
	return ;
}

bool check(int v)
{
	mark[v] = 1;
	bool ret = 1;
	if (nos[c[v]] > 1)
	{
		ret = 0;
	}
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		ret &= check(u);
	}
	mark[v] = 0;
	return ret;
}

int solve(int v, int sz)
{
	if (sz == 1)
	{
		return 0;
	}
	v = find(v, sz);
	p[v] = 0;
	find(v, 0);

	queue <int> q, qq;
	for (auto o : poec[c[v]])
	{
		q.push(o);
		qq.push(o);
	}
	s[c[v]] = 1;
	int ans = 0;
	while (q.size())
	{
		int v = q.front();
		while (v and mark[v] == 0)
		{
			mark[v] = 1;
			qq.push(v);
			if (!s[c[v]])
			{
				ans++;
				s[c[v]] = 1;
				for (auto o : poec[c[v]])
				{
					q.push(o);
					qq.push(o);
				}
			}
			v = p[v];
		}
		q.pop();
	}

	while (qq.size())
	{
		int o = qq.front();
		mark[o] = 0;
		s[c[o]] = 0;
		qq.pop();
	}

	mark[v] = 1;

	nos[c[v]] = 2;

	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		dfs(u, 1);
		dfs(u, 0);
	}

	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		if (check(u))
		{
			ans = min(ans, solve(u, vu[u]));
		}
	}
	return ans;
}

int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 1;i < n;i++)
	{
		int v, u;
		cin >> v >> u;
		ne[v].push_back(u);
		ne[u].push_back(v);
	}

	for (int i = 1;i <= n;i++)
	{
		cin >> c[i];
		poec[c[i]].push_back(i);
	}
	cout << solve(1, n);
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59