답안 #220614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220614	2020-04-08T09:00:41 Z	atoiz	Mergers (JOI19_mergers)	C++14	0 / 100	83 ms	31728 KB

mergers

/*input
2 2
1 2
1
2
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 500007;
int N, K, open = 0, ans = 0;
int dsu[MAXN], group[MAXN], last[MAXN], val[MAXN];
vector<int> adj[MAXN], add[MAXN];

int root(int u) { return (dsu[u] != u ? dsu[u] = root(dsu[u]) : u); }

void dfs(int u, int p)
{
	dsu[u] = u;
	for (int v : add[u]) {
		if (dsu[v]) val[root(v)] -= 2;
	}

	for (int v : adj[u]) if (v != p) {
		dfs(v, u);
		dsu[v] = u;
		val[u] += val[v];
	}

	if (u != 1 && !val[u]) ++val[u], ++ans;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N - 1; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int u = 1; u <= N; ++u) {
		cin >> group[u];
		if (last[group[u]]) {
			int v = last[group[u]];
			add[u].push_back(v);
			add[v].push_back(u);
			++val[u], ++val[v];
		}
		last[group[u]] = u;
	}
	dfs(1, 0);
	cout << (ans + 1) / 2 << endl;
	return 0;
}

Subtask #1

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	23808 KB	Output is correct
2	Correct	18 ms	23936 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	17 ms	23936 KB	Output is correct
6	Correct	18 ms	23808 KB	Output is correct
7	Correct	18 ms	23808 KB	Output is correct
8	Correct	18 ms	23936 KB	Output is correct
9	Correct	17 ms	23936 KB	Output is correct
10	Correct	16 ms	23936 KB	Output is correct
11	Correct	18 ms	23808 KB	Output is correct
12	Correct	17 ms	23808 KB	Output is correct
13	Correct	18 ms	23808 KB	Output is correct
14	Correct	18 ms	23808 KB	Output is correct
15	Correct	18 ms	23808 KB	Output is correct
16	Incorrect	17 ms	23936 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	23808 KB	Output is correct
2	Correct	18 ms	23936 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	17 ms	23936 KB	Output is correct
6	Correct	18 ms	23808 KB	Output is correct
7	Correct	18 ms	23808 KB	Output is correct
8	Correct	18 ms	23936 KB	Output is correct
9	Correct	17 ms	23936 KB	Output is correct
10	Correct	16 ms	23936 KB	Output is correct
11	Correct	18 ms	23808 KB	Output is correct
12	Correct	17 ms	23808 KB	Output is correct
13	Correct	18 ms	23808 KB	Output is correct
14	Correct	18 ms	23808 KB	Output is correct
15	Correct	18 ms	23808 KB	Output is correct
16	Incorrect	17 ms	23936 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	23808 KB	Output is correct
2	Correct	18 ms	23936 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	17 ms	23936 KB	Output is correct
6	Correct	18 ms	23808 KB	Output is correct
7	Correct	18 ms	23808 KB	Output is correct
8	Correct	18 ms	23936 KB	Output is correct
9	Correct	17 ms	23936 KB	Output is correct
10	Correct	16 ms	23936 KB	Output is correct
11	Correct	18 ms	23808 KB	Output is correct
12	Correct	17 ms	23808 KB	Output is correct
13	Correct	18 ms	23808 KB	Output is correct
14	Correct	18 ms	23808 KB	Output is correct
15	Correct	18 ms	23808 KB	Output is correct
16	Incorrect	17 ms	23936 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	31728 KB	Output is correct
2	Incorrect	70 ms	28912 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	23808 KB	Output is correct
2	Correct	18 ms	23936 KB	Output is correct
3	Correct	18 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	17 ms	23936 KB	Output is correct
6	Correct	18 ms	23808 KB	Output is correct
7	Correct	18 ms	23808 KB	Output is correct
8	Correct	18 ms	23936 KB	Output is correct
9	Correct	17 ms	23936 KB	Output is correct
10	Correct	16 ms	23936 KB	Output is correct
11	Correct	18 ms	23808 KB	Output is correct
12	Correct	17 ms	23808 KB	Output is correct
13	Correct	18 ms	23808 KB	Output is correct
14	Correct	18 ms	23808 KB	Output is correct
15	Correct	18 ms	23808 KB	Output is correct
16	Incorrect	17 ms	23936 KB	Output isn't correct
17	Halted	0 ms	0 KB	-