제출 #109762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109762		luciocf	Mergers (JOI19_mergers)	C++14	0 / 100	3086 ms	15244 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n, k;

int pai[maxn], peso[maxn];

int s[maxn];

int par[maxn], grau[maxn];

bool mark[maxn];

vector<int> grafo[maxn], state[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;

		par[v] = u;
		dfs(v, u);
	}
}

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();

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

		par[i] = 0;
		dfs(i, 0);

		for (auto v: state[s[i]])
		{
			while (v != i)
			{
				Join(i, v);
				v = par[v];
			}
		}
	}

	for (int i = 1; i <= n; i++)
		for (auto v: grafo[i])
			if (Find(v) != Find(i))
				grau[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:54: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:59: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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~

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