Submission #167281

#	Time	Username	Problem	Language	Result	Execution time	Memory
167281		maruii	Mergers (JOI19_mergers)	C++14	100 / 100	976 ms	91044 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], D[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;;

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 <= N; ++i) D[i] = edge[i].size();
	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 = u1.fnd(vec[i][j]), y = u1.fnd(vec[i][j + 1]);
			while (x != y) {
				int a, b;
				if (dep[x] < dep[y]) {
					int t = u1.fnd(par[y]);
					if (y != t) {
						D[y]--;
						D[t]--;
						u1.par[y] = t;
						D[t] += D[y];
					}
					y = t;
				}
				else {
					int t = u1.fnd(par[x]);
					if (x != t) {
						D[x]--;
						D[t]--;
						u1.par[x] = t;
						D[t] += D[x];
					}
					x = t;
				}
			}
		}
	}
	int ans = 1;
	for (int i = 1; i <= N; ++i) {
		int t = u1.fnd(i);
		if (A[t] == 0 && D[t] == 1) A[t] = 1, ans++;
	}
	cout << ans / 2;
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:42:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vec[i].size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~~~~
mergers.cpp:45:9: warning: unused variable 'a' [-Wunused-variable]
     int a, b;
         ^
mergers.cpp:45:12: warning: unused variable 'b' [-Wunused-variable]
     int a, b;
            ^

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