Submission #167273

#	Time	Username	Problem	Language	Result	Execution time	Memory
167273		maruii	Mergers (JOI19_mergers)	C++14	0 / 100	110 ms	37872 KiB

mergers

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

vector<int> edge[500005], vec[500005];
int dfn[500005], dfnn, C[500005], par[500005], dep[500005];
bool A[500005];

struct UF {
	int par[500005];
	UF() { iota(par, par + 500005, 0); }
	int fnd(int x) { return par[x] == x ? x : par[x] = fnd(par[x]); }
} u1, u2;

void dfs(int x, int p) {
	par[x] = p;
	dep[x] = dep[p] + 1;
	dfn[x] = ++dfnn;
	for (auto i : edge[x]) {
		if (i == p) continue;
		dfs(i, x);
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M; cin >> N >> M;
	for (int i = 1; i < N; ++i) {
		int x, y; cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	dfs(1, 1);
	for (int i = 1; i <= N; ++i) {
		cin >> C[i];
		vec[C[i]].push_back(i);
	}
	for (int i = 1; i <= M; ++i) {
		sort(vec[i].begin(), vec[i].end(), [&](int a, int b) {
			return dfn[a] < dfn[b];
		});
		for (int j = 0; j + 1 < vec[i].size(); ++j) {
			int x = u2.fnd(vec[i][j]), y = u2.fnd(vec[i][j + 1]);
			while (x != y) {
				int a, b;
				if (dep[x] < dep[y]) {
					u2.par[y] = u2.fnd(par[y]);
					a = u1.fnd(C[par[y]]), b = u1.fnd(i);
					y = u2.fnd(y);
				}
				else {
					u2.par[x] = u2.fnd(par[x]);
					a = u1.fnd(C[par[x]]), b = u1.fnd(i);
					x = u2.fnd(x);
				}
				if (a != b) u1.par[a] = b;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; ++i) if (edge[i].size() == 1 && !A[u1.fnd(C[i])]) A[u1.fnd(C[i])] = 1, ans++;
	cout << ans / 2;
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:41:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vec[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~

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