답안 #109766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109766	2019-05-08T03:39:07 Z	luciocf	Mergers (JOI19_mergers)	C++14	56 / 100	3000 ms	25336 KB

mergers

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxl = 20;

int n, k;

int pai[maxn], peso[maxn];

int s[maxn];

int nivel[maxn];
int tab[maxn][maxl];

int grau[maxn];

bool mark[maxn];

vector<int> grafo[maxn], state[maxn];

void init(void)
{
	for (int i = 1; i <= n; i++)
		pai[i] = i, peso[i] = 1;
}

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void dfs(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		nivel[v] = nivel[u]+1, tab[v][0] = u;
		dfs(v, u);
	}
}

void build(void)
{
	for (int j = 1; j < maxl; j++)
		for (int i = 1; i <= n; i++)
			tab[i][j] = tab[tab[i][j-1]][j-1];
}

int lca(int u, int v)
{
	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = maxl-1; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			u = tab[u][i];

	if (u == v) return u;

	for (int i = maxl-1; i >= 0; i--)
		if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
			u = tab[u][i], v = tab[v][i];

	return tab[u][0];
}

int main(void)
{
	scanf("%d %d", &n, &k);

	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &s[i]);

		state[s[i]].push_back(i);
	}

	init();

	nivel[1] = 1;
	dfs(1, 0); build();

	for (int i = 1; i <= n; i++)
	{
		if (mark[s[i]]) continue;
		mark[s[i]] = 1;

		for (auto j: state[s[i]])
		{
			int v = j;
			int l = lca(i, v);
			
			while (nivel[v] >= nivel[l])
			{
				Join(i, v);
				v = tab[v][0];
			}

			v = i;

			while (nivel[v] >= nivel[l])
			{
				Join(i, v);
				v = tab[v][0];
			}
		}
	}

	for (int i = 1; i <= n; i++)
		for (auto v: grafo[i])
			if (Find(v) != Find(i))
				grau[Find(v)]++;

	int leaf = 0;

	for (int i = 1; i <= n; i++)
		if (grau[i] == 1)
			leaf++;

	printf("%d\n", (leaf+1)/2);
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5120 KB	Output is correct
2	Correct	6 ms	5120 KB	Output is correct
3	Correct	7 ms	4992 KB	Output is correct
4	Correct	7 ms	5120 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	6 ms	5120 KB	Output is correct
8	Correct	7 ms	5120 KB	Output is correct
9	Correct	6 ms	5120 KB	Output is correct
10	Correct	6 ms	5120 KB	Output is correct
11	Correct	7 ms	5120 KB	Output is correct
12	Correct	6 ms	5120 KB	Output is correct
13	Correct	8 ms	4992 KB	Output is correct
14	Correct	6 ms	4992 KB	Output is correct
15	Correct	7 ms	4992 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	6 ms	4988 KB	Output is correct
19	Correct	5 ms	4992 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	8 ms	5120 KB	Output is correct
23	Correct	6 ms	5120 KB	Output is correct
24	Correct	7 ms	5120 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5120 KB	Output is correct
2	Correct	6 ms	5120 KB	Output is correct
3	Correct	7 ms	4992 KB	Output is correct
4	Correct	7 ms	5120 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	6 ms	5120 KB	Output is correct
8	Correct	7 ms	5120 KB	Output is correct
9	Correct	6 ms	5120 KB	Output is correct
10	Correct	6 ms	5120 KB	Output is correct
11	Correct	7 ms	5120 KB	Output is correct
12	Correct	6 ms	5120 KB	Output is correct
13	Correct	8 ms	4992 KB	Output is correct
14	Correct	6 ms	4992 KB	Output is correct
15	Correct	7 ms	4992 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	6 ms	4988 KB	Output is correct
19	Correct	5 ms	4992 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	8 ms	5120 KB	Output is correct
23	Correct	6 ms	5120 KB	Output is correct
24	Correct	7 ms	5120 KB	Output is correct
25	Correct	7 ms	5120 KB	Output is correct
26	Correct	12 ms	5504 KB	Output is correct
27	Correct	9 ms	5376 KB	Output is correct
28	Correct	8 ms	5632 KB	Output is correct
29	Correct	9 ms	5504 KB	Output is correct
30	Correct	10 ms	5504 KB	Output is correct
31	Correct	6 ms	5120 KB	Output is correct
32	Correct	9 ms	5632 KB	Output is correct
33	Correct	7 ms	4992 KB	Output is correct
34	Correct	9 ms	5504 KB	Output is correct
35	Correct	9 ms	5476 KB	Output is correct
36	Correct	11 ms	5504 KB	Output is correct
37	Correct	10 ms	5504 KB	Output is correct
38	Correct	7 ms	5120 KB	Output is correct
39	Correct	9 ms	5552 KB	Output is correct
40	Correct	9 ms	5504 KB	Output is correct
41	Correct	8 ms	5504 KB	Output is correct
42	Correct	8 ms	5504 KB	Output is correct
43	Correct	63 ms	5760 KB	Output is correct
44	Correct	7 ms	5120 KB	Output is correct
45	Correct	10 ms	5632 KB	Output is correct
46	Correct	9 ms	5504 KB	Output is correct
47	Correct	6 ms	5120 KB	Output is correct
48	Correct	10 ms	5504 KB	Output is correct
49	Correct	9 ms	5632 KB	Output is correct
50	Correct	11 ms	5632 KB	Output is correct
51	Correct	10 ms	5504 KB	Output is correct
52	Correct	8 ms	5504 KB	Output is correct
53	Correct	9 ms	5504 KB	Output is correct
54	Correct	9 ms	5376 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5120 KB	Output is correct
2	Correct	6 ms	5120 KB	Output is correct
3	Correct	7 ms	4992 KB	Output is correct
4	Correct	7 ms	5120 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	6 ms	5120 KB	Output is correct
8	Correct	7 ms	5120 KB	Output is correct
9	Correct	6 ms	5120 KB	Output is correct
10	Correct	6 ms	5120 KB	Output is correct
11	Correct	7 ms	5120 KB	Output is correct
12	Correct	6 ms	5120 KB	Output is correct
13	Correct	8 ms	4992 KB	Output is correct
14	Correct	6 ms	4992 KB	Output is correct
15	Correct	7 ms	4992 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	6 ms	4988 KB	Output is correct
19	Correct	5 ms	4992 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	8 ms	5120 KB	Output is correct
23	Correct	6 ms	5120 KB	Output is correct
24	Correct	7 ms	5120 KB	Output is correct
25	Correct	6 ms	4992 KB	Output is correct
26	Correct	131 ms	18544 KB	Output is correct
27	Correct	199 ms	18204 KB	Output is correct
28	Correct	9 ms	5504 KB	Output is correct
29	Correct	6 ms	5120 KB	Output is correct
30	Correct	5 ms	4992 KB	Output is correct
31	Correct	137 ms	18040 KB	Output is correct
32	Correct	8 ms	5504 KB	Output is correct
33	Execution timed out	3043 ms	22364 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	135 ms	18444 KB	Output is correct
2	Correct	131 ms	21616 KB	Output is correct
3	Correct	11 ms	5632 KB	Output is correct
4	Correct	11 ms	5504 KB	Output is correct
5	Correct	8 ms	5120 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	9 ms	5504 KB	Output is correct
8	Correct	219 ms	21372 KB	Output is correct
9	Correct	9 ms	5504 KB	Output is correct
10	Correct	140 ms	19832 KB	Output is correct
11	Correct	6 ms	5120 KB	Output is correct
12	Correct	193 ms	19812 KB	Output is correct
13	Correct	268 ms	21240 KB	Output is correct
14	Correct	162 ms	22964 KB	Output is correct
15	Correct	121 ms	19944 KB	Output is correct
16	Correct	10 ms	5504 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	138 ms	23024 KB	Output is correct
19	Correct	199 ms	25336 KB	Output is correct
20	Correct	11 ms	5504 KB	Output is correct
21	Correct	6 ms	5120 KB	Output is correct
22	Correct	149 ms	21668 KB	Output is correct
23	Correct	36 ms	5520 KB	Output is correct
24	Correct	190 ms	20316 KB	Output is correct
25	Correct	193 ms	24568 KB	Output is correct
26	Correct	11 ms	5632 KB	Output is correct
27	Correct	10 ms	5632 KB	Output is correct
28	Correct	9 ms	5504 KB	Output is correct
29	Correct	9 ms	5504 KB	Output is correct
30	Correct	10 ms	5632 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5120 KB	Output is correct
2	Correct	6 ms	5120 KB	Output is correct
3	Correct	7 ms	4992 KB	Output is correct
4	Correct	7 ms	5120 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	6 ms	5120 KB	Output is correct
8	Correct	7 ms	5120 KB	Output is correct
9	Correct	6 ms	5120 KB	Output is correct
10	Correct	6 ms	5120 KB	Output is correct
11	Correct	7 ms	5120 KB	Output is correct
12	Correct	6 ms	5120 KB	Output is correct
13	Correct	8 ms	4992 KB	Output is correct
14	Correct	6 ms	4992 KB	Output is correct
15	Correct	7 ms	4992 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	6 ms	4988 KB	Output is correct
19	Correct	5 ms	4992 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	8 ms	5120 KB	Output is correct
23	Correct	6 ms	5120 KB	Output is correct
24	Correct	7 ms	5120 KB	Output is correct
25	Correct	7 ms	5120 KB	Output is correct
26	Correct	12 ms	5504 KB	Output is correct
27	Correct	9 ms	5376 KB	Output is correct
28	Correct	8 ms	5632 KB	Output is correct
29	Correct	9 ms	5504 KB	Output is correct
30	Correct	10 ms	5504 KB	Output is correct
31	Correct	6 ms	5120 KB	Output is correct
32	Correct	9 ms	5632 KB	Output is correct
33	Correct	7 ms	4992 KB	Output is correct
34	Correct	9 ms	5504 KB	Output is correct
35	Correct	9 ms	5476 KB	Output is correct
36	Correct	11 ms	5504 KB	Output is correct
37	Correct	10 ms	5504 KB	Output is correct
38	Correct	7 ms	5120 KB	Output is correct
39	Correct	9 ms	5552 KB	Output is correct
40	Correct	9 ms	5504 KB	Output is correct
41	Correct	8 ms	5504 KB	Output is correct
42	Correct	8 ms	5504 KB	Output is correct
43	Correct	63 ms	5760 KB	Output is correct
44	Correct	7 ms	5120 KB	Output is correct
45	Correct	10 ms	5632 KB	Output is correct
46	Correct	9 ms	5504 KB	Output is correct
47	Correct	6 ms	5120 KB	Output is correct
48	Correct	10 ms	5504 KB	Output is correct
49	Correct	9 ms	5632 KB	Output is correct
50	Correct	11 ms	5632 KB	Output is correct
51	Correct	10 ms	5504 KB	Output is correct
52	Correct	8 ms	5504 KB	Output is correct
53	Correct	9 ms	5504 KB	Output is correct
54	Correct	9 ms	5376 KB	Output is correct
55	Correct	6 ms	4992 KB	Output is correct
56	Correct	131 ms	18544 KB	Output is correct
57	Correct	199 ms	18204 KB	Output is correct
58	Correct	9 ms	5504 KB	Output is correct
59	Correct	6 ms	5120 KB	Output is correct
60	Correct	5 ms	4992 KB	Output is correct
61	Correct	137 ms	18040 KB	Output is correct
62	Correct	8 ms	5504 KB	Output is correct
63	Execution timed out	3043 ms	22364 KB	Time limit exceeded
64	Halted	0 ms	0 KB	-

답안 #109766

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 14.0

Subtask #4 22.0 / 22.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 14.0

Subtask #4
22.0 / 22.0

Subtask #5
0 / 30.0