Submission #377743

#	Time	Username	Problem	Language	Result	Execution time	Memory
377743		peijar	Mergers (JOI19_mergers)	C++17	0 / 100	73 ms	17864 KiB

mergers

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

vector<vector<int>> adj;
vector<int> etat;
vector<vector<int>> dansEtat;
vector<int> profondeur;
vector<int> parent;
vector<int> id;
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;
	id.resize(nbSommets);
	for (int i(0); i < nbSommets; ++i)
		id[i] = i;
	adj.resize(nbSommets);
	etat.resize(nbSommets);
	dansEtat.resize(nbEtats);
	parent.resize(nbSommets);
	profondeur.resize(nbSommets);
	for (int i(1); i < nbSommets; ++i)
	{
		int u, v;
		cin >> u >> v;
		--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];
			}
		}
	}
	for (int iSommet = 0; iSommet < nbSommets; ++iSommet) 
	{
		//cout << iSommet+1 << ' ' << find(iSommet) + 1 << endl;
	}
	vector<int> deg(nbSommets);
	for (int iSommet = 0; iSommet < nbSommets; ++iSommet) 
		for (auto iVoisin : adj[iSommet])
			if (iVoisin != parent[iSommet] and find(iSommet) != find(iVoisin))
				deg[find(iSommet)]++;
	int nbFeuilles(0);
	for (int iSommet = 0; iSommet < nbSommets; ++iSommet) 
		if (find(iSommet) == iSommet)
			nbFeuilles += !deg[iSommet];
	if (deg[0] == 1)
		nbFeuilles++;
	cout << nbFeuilles - 1 << endl;
}

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