제출 #377746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377746		peijar	Mergers (JOI19_mergers)	C++17	100 / 100	863 ms	101576 KiB

mergers

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

const int MAXN = 5e5;
vector<int> adj[MAXN], dansEtat[MAXN];
int etat[MAXN], profondeur[MAXN], parent[MAXN], id[MAXN];
int nbSommets, nbEtats;

void dfs(int u, int p)
{
	for (auto v : adj[u])
		if (v != p)
		{
			profondeur[v] = profondeur[u] + 1;
			parent[v] = u;
			dfs(v, u);
		}
}

int find(int u)
{
	return id[u] = (u == id[u] ? u : find(id[u]));
}

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> nbSommets >> nbEtats;
	vector<pair<int, int>> aretes;
	for (int i(0); i < nbSommets; ++i)
		id[i] = i;
	for (int i(1); i < nbSommets; ++i)
	{
		int u, v;
		cin >> u >> v;
		--u, --v;
		aretes.emplace_back(u, v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i(0); i < nbSommets; ++i)
	{
		cin >> etat[i];
		--etat[i];
		dansEtat[etat[i]].push_back(i);
	}

	dfs(0, 0);

	for (int iEtat(0); iEtat < nbEtats; ++iEtat)
	{
		for (int i(1); i < (int)dansEtat[iEtat].size(); ++i)
		{
			int u = dansEtat[iEtat][i-1], v = dansEtat[iEtat][i];
			u = find(u), v = find(v);
			while (u != v)
			{
				if (profondeur[u] < profondeur[v]) swap(u, v);
				id[u] = find(id[parent[u]]);
				u = id[u];
			}
		}
	}
	vector<int> deg(nbSommets);
	for (auto [u, v] : aretes)
	{
		u = find(u), v = find(v);
		if (u != v)
			deg[u]++, deg[v]++;
	}
	int nbFeuilles(0);
	for (auto d : deg)
		nbFeuilles += d == 1;
	int sol = (nbFeuilles + 1)/2;
	cout << sol << endl;
}

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