제출 #109998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109998		luciocf	Mergers (JOI19_mergers)	C++14	70 / 100	1688 ms	78848 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxk = 55;
const int maxl = 20;

int n, k;

int pai[maxn], peso[maxn];

int s[maxn];

int nivel[maxn];
int tab[maxn][maxl];

int grau[maxn];

bool mark[maxn];

vector<int> grafo[maxn], state[maxn];

int sub[maxk][maxn];

void init(void)
{
	for (int i = 1; i <= n; i++)
		pai[i] = i, peso[i] = 1;
}

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void dfs(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		nivel[v] = nivel[u]+1, tab[v][0] = u;
		dfs(v, u);
	}
}

void build(void)
{
	for (int j = 1; j < maxl; j++)
		for (int i = 1; i <= n; i++)
			tab[i][j] = tab[tab[i][j-1]][j-1];
}

int lca(int u, int v)
{
	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = maxl-1; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			u = tab[u][i];

	if (u == v) return u;

	for (int i = maxl-1; i >= 0; i--)
		if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
			u = tab[u][i], v = tab[v][i];

	return tab[u][0];
}

void dfs2(int u, int p, int q)
{
	if (s[u] == q) 
		sub[q][u]++;

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		dfs2(v, u, q);

		sub[q][u] += sub[q][v];
	}
}

void solve(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		solve(v, u);

		bool ok = 1;

		for (int i = 1; i <= k; i++)
			if (sub[i][v] > 0 && sub[i][1] > sub[i][v])
				ok = 0;

		if (!ok)
			Join(v, u);
	}
}

void small_k(void)
{
	for (int i = 1; i <= k; i++)
		dfs2(1, 0, i);

	solve(1, 0);

	for (int i = 1; i <= n; i++)
		for (auto v: grafo[i])
			if (Find(v) != Find(i))
				grau[Find(v)]++;

	int leaf = 0;

	for (int i = 1; i <= n; i++)
		if (grau[i] == 1)
			leaf++;

	printf("%d\n", (leaf+1)/2);
}

int main(void)
{
	scanf("%d %d", &n, &k);

	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &s[i]);

		state[s[i]].push_back(i);
	}

	init();

	if (k <= 50)
	{
		small_k();
		return 0;
	}

	nivel[1] = 1;
	dfs(1, 0); build();

	for (int i = 1; i <= n; i++)
	{
		if (mark[s[i]]) continue;
		mark[s[i]] = 1;

		for (auto j: state[s[i]])
		{
			int v = j;
			int l = lca(i, v);
			
			while (nivel[v] >= nivel[l])
			{
				Join(i, v);
				v = tab[v][0];
			}

			v = i;

			while (nivel[v] >= nivel[l])
			{
				Join(i, v);
				v = tab[v][0];
			}
		}
	}

	for (int i = 1; i <= n; i++)
		for (auto v: grafo[i])
			if (Find(v) != Find(i))
				grau[Find(v)]++;

	int leaf = 0;

	for (int i = 1; i <= n; i++)
		if (grau[i] == 1)
			leaf++;

	printf("%d\n", (leaf+1)/2);
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'int main()':
mergers.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 0 / 30