oj.uz

Submission #167276

# Submission time Handle Problem Language Result Execution time Memory
167276 2019-12-07T07:45:59 Z maruii Mergers (JOI19_mergers) C++14
0 / 100
 110 ms 34456 KB 
#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];

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 = u1.fnd(y);
				}
				else {
					int t = u1.fnd(par[x]);
					if (x != t) {
						D[x]--;
						D[t]--;
						u1.par[x] = t;
						D[t] += D[x];
					}
					x = u1.fnd(x);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; ++i) ans += D[i] == 1;
	cout << ans / 2;
	return 0;
}

Compilation message

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) {
                   ~~~~~~^~~~~~~~~~~~~~~
mergers.cpp:44:9: warning: unused variable 'a' [-Wunused-variable]
     int a, b;
         ^
mergers.cpp:44:12: warning: unused variable 'b' [-Wunused-variable]
     int a, b;
            ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25848 KB Output is correct
2 Incorrect 27 ms 25848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25848 KB Output is correct
2 Incorrect 27 ms 25848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25848 KB Output is correct
2 Incorrect 27 ms 25848 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 31984 KB Output is correct
2 Incorrect 110 ms 34456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25848 KB Output is correct
2 Incorrect 27 ms 25848 KB Output isn't correct
3 Halted 0 ms 0 KB -