oj.uz

Submission #377743

# Submission time Handle Problem Language Result Execution time Memory
377743 2021-03-14T22:25:57 Z peijar Mergers (JOI19_mergers) C++17
0 / 100
 73 ms 17864 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 13152 KB Output is correct
2 Incorrect 73 ms 17864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -