Submission #1097384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097384	2024-10-07T06:59:35 Z	Alihan_8	Mergers (JOI19_mergers)	C++17	48 / 100	148 ms	262144 KB

mergers

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, k; cin >> n >> k;
	
	vector <vector<int>> adj(n);
	
	for ( int i = 0; i + 1 < n; i++ ){
		int u, v; cin >> u >> v;
		
		--u, --v;
		
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	vector <int> s(n);
	
	for ( auto &x: s ){
		cin >> x; --x;
	}

	vector <vector<int>> cnt(n, vector <int> (k));
	
	auto dfs = [&](auto dfs, int u, int p) -> void{
		cnt[u][s[u]] = 1;
		
		for ( auto &v: adj[u] ){
			if ( v != p ){
				dfs(dfs, v, u);
				
				for ( int i = 0; i < k; i++ ){
					cnt[u][i] += cnt[v][i];
				}
			}
		}
	};
	
	dfs(dfs, 0, -1);
	
	vector <int> bad(n);
	
	for ( int u = 0; u < n; u++ ){
		bool flag = true;
		
		for ( int t = 0; t < k; t++ ){
			if ( cnt[u][t] > 0 && cnt[u][t] < cnt[0][t] ){
				flag = false;
			}
		}
		
		bad[u] = flag;
	}
	
	vector <int> sub(n);
	
	bad[0] = 0;
	
	auto cals = [&](auto cals, int u, int p) -> void{
		sub[u] = bad[u];
		
		for ( auto &v: adj[u] ){
			if ( v != p ){
				cals(cals, v, u);
				
				sub[u] += sub[v];
			}
		}
	};
	
	cals(cals, 0, -1);
	
	int num = 0;
	
	for ( int u = 1; u < n; u++ ){
		if ( !bad[u] ) continue;
		
		if ( sub[u] == sub[0] || sub[u] == 1 ){
			num += 1;
		}
	}
	
	cout << (num + 1) / 2;
	
	cout << '\n';
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct

Subtask #2
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	20 ms	24292 KB	Output is correct
27	Correct	2 ms	1372 KB	Output is correct
28	Correct	37 ms	35884 KB	Output is correct
29	Correct	29 ms	35928 KB	Output is correct
30	Correct	3 ms	3416 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	38 ms	36080 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	1 ms	1372 KB	Output is correct
35	Correct	29 ms	35928 KB	Output is correct
36	Correct	2 ms	1372 KB	Output is correct
37	Correct	15 ms	18348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	15 ms	18412 KB	Output is correct
40	Correct	2 ms	604 KB	Output is correct
41	Correct	1 ms	860 KB	Output is correct
42	Correct	16 ms	18256 KB	Output is correct
43	Correct	1 ms	860 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	30 ms	34888 KB	Output is correct
46	Correct	15 ms	18008 KB	Output is correct
47	Correct	0 ms	348 KB	Output is correct
48	Correct	6 ms	7772 KB	Output is correct
49	Correct	37 ms	36040 KB	Output is correct
50	Correct	34 ms	35928 KB	Output is correct
51	Correct	6 ms	7772 KB	Output is correct
52	Correct	1 ms	1372 KB	Output is correct
53	Correct	15 ms	18412 KB	Output is correct
54	Correct	2 ms	1180 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	54 ms	31628 KB	Output is correct
27	Correct	76 ms	31312 KB	Output is correct
28	Correct	2 ms	1372 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	76 ms	31344 KB	Output is correct
32	Correct	2 ms	1372 KB	Output is correct
33	Correct	85 ms	35232 KB	Output is correct
34	Correct	69 ms	31316 KB	Output is correct
35	Correct	2 ms	1372 KB	Output is correct
36	Correct	74 ms	31600 KB	Output is correct
37	Correct	2 ms	860 KB	Output is correct
38	Correct	2 ms	856 KB	Output is correct
39	Correct	66 ms	31560 KB	Output is correct
40	Correct	2 ms	860 KB	Output is correct
41	Correct	37 ms	13904 KB	Output is correct
42	Correct	79 ms	32596 KB	Output is correct
43	Correct	0 ms	344 KB	Output is correct
44	Correct	46 ms	18184 KB	Output is correct
45	Correct	72 ms	33360 KB	Output is correct
46	Correct	2 ms	1372 KB	Output is correct
47	Correct	2 ms	1144 KB	Output is correct

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	31436 KB	Output is correct
2	Runtime error	148 ms	262144 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	20 ms	24292 KB	Output is correct
27	Correct	2 ms	1372 KB	Output is correct
28	Correct	37 ms	35884 KB	Output is correct
29	Correct	29 ms	35928 KB	Output is correct
30	Correct	3 ms	3416 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	38 ms	36080 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	1 ms	1372 KB	Output is correct
35	Correct	29 ms	35928 KB	Output is correct
36	Correct	2 ms	1372 KB	Output is correct
37	Correct	15 ms	18348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	15 ms	18412 KB	Output is correct
40	Correct	2 ms	604 KB	Output is correct
41	Correct	1 ms	860 KB	Output is correct
42	Correct	16 ms	18256 KB	Output is correct
43	Correct	1 ms	860 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	30 ms	34888 KB	Output is correct
46	Correct	15 ms	18008 KB	Output is correct
47	Correct	0 ms	348 KB	Output is correct
48	Correct	6 ms	7772 KB	Output is correct
49	Correct	37 ms	36040 KB	Output is correct
50	Correct	34 ms	35928 KB	Output is correct
51	Correct	6 ms	7772 KB	Output is correct
52	Correct	1 ms	1372 KB	Output is correct
53	Correct	15 ms	18412 KB	Output is correct
54	Correct	2 ms	1180 KB	Output is correct
55	Correct	1 ms	348 KB	Output is correct
56	Correct	54 ms	31628 KB	Output is correct
57	Correct	76 ms	31312 KB	Output is correct
58	Correct	2 ms	1372 KB	Output is correct
59	Correct	0 ms	348 KB	Output is correct
60	Correct	0 ms	348 KB	Output is correct
61	Correct	76 ms	31344 KB	Output is correct
62	Correct	2 ms	1372 KB	Output is correct
63	Correct	85 ms	35232 KB	Output is correct
64	Correct	69 ms	31316 KB	Output is correct
65	Correct	2 ms	1372 KB	Output is correct
66	Correct	74 ms	31600 KB	Output is correct
67	Correct	2 ms	860 KB	Output is correct
68	Correct	2 ms	856 KB	Output is correct
69	Correct	66 ms	31560 KB	Output is correct
70	Correct	2 ms	860 KB	Output is correct
71	Correct	37 ms	13904 KB	Output is correct
72	Correct	79 ms	32596 KB	Output is correct
73	Correct	0 ms	344 KB	Output is correct
74	Correct	46 ms	18184 KB	Output is correct
75	Correct	72 ms	33360 KB	Output is correct
76	Correct	2 ms	1372 KB	Output is correct
77	Correct	2 ms	1144 KB	Output is correct
78	Correct	65 ms	31436 KB	Output is correct
79	Runtime error	148 ms	262144 KB	Execution killed with signal 9
80	Halted	0 ms	0 KB	-

Submission #1097384

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 24.0 / 24.0

Subtask #3 14.0 / 14.0

Subtask #4 0 / 22.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
24.0 / 24.0

Subtask #3
14.0 / 14.0

Subtask #4
0 / 22.0

Subtask #5
0 / 30.0