Submission #102942

#	Time	Username	Problem	Language	Result	Execution time	Memory
102942		hugo_pm	Mergers (JOI19_mergers)	C++17	100 / 100	1262 ms	95076 KiB

mergers

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

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }

void cpr(string s) { cpr(s, {}); }

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 505*1000;
int drepr[borne];

int dfind(int x)
{
	if (drepr[x] == x) return x;
	else return drepr[x] = dfind(drepr[x]);
}

void dunir(int a, int b) // merge a dans b, b est le parent
{
	a = dfind(a); b = dfind(b);
	if (a == b) return;
	drepr[a] = b;
}

// ww

int nbNoeuds, nbEtats;
int par[borne], prof[borne];
vector<int> adj[borne];
int gpOfNod[borne];
int deg[borne];
vector<int> nodInGp[borne];

void combiner(int a, int b)
{
	a = dfind(a); b = dfind(b);
	while (a != b) {
		if (prof[a] < prof[b]) swap(a,b);
		dunir(a, par[a]);
		a = dfind(a);
	}
}

void dfsInit(int nod)
{
	for (int vo : adj[nod]) if (vo != par[nod]) {
		par[vo] = nod;
		prof[vo] = prof[nod] + 1;
		dfsInit(vo);
	}
}

void solve()
{
	form(i, borne) { drepr[i] = i; par[i] = -1; }
	cin >> nbNoeuds >> nbEtats;
	form(i, nbNoeuds-1) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	prof[0] = 0;
	dfsInit(0);

	form(nod, nbNoeuds) {
		cin >> gpOfNod[nod]; --gpOfNod[nod];
		nodInGp[gpOfNod[nod]].push_back(nod);
	}

	form(grp, nbEtats) {
		int sz = nodInGp[grp].size();
		form2(i, 1, sz) {
			combiner(nodInGp[grp][0], nodInGp[grp][i]);
		}
	}

	form(nod, nbNoeuds) {
		for (int vo : adj[nod]) {
			if (dfind(nod) != dfind(vo)) ++deg[dfind(nod)];
		}
	}

	int lf = 0;
	form(nod, nbNoeuds) if (dfind(nod) == nod && deg[nod] == 1) ++lf;
	cout << (lf+1)/2 << "\n";
}

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