답안 #229769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229769	2020-05-06T10:09:33 Z	someone_aa	수도 (JOI20_capital_city)	C++17	100 / 100	1000 ms	40892 KB

capital_city

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
using namespace std;
const int maxn = 200100;
int n, k;

vector<int>g[maxn], towns[maxn];
int city[maxn], cnt[maxn];

int usize[maxn], uparent[maxn];

int ufind(int node) {
	while(node != uparent[node]) {
		node = uparent[node];
	}
	return node;
}

bool unite(int a, int b) {
	a = ufind(a);
	b = ufind(b);

	if(a == b) return false;
	
	if(usize[a] > usize[b]) {
		uparent[b] = a;
		usize[a] += usize[b];
	}
	else {
		uparent[a] = b;
		usize[b] += usize[a];
	}
	return true;
}

bool deleted[maxn];
int sbt_sz[maxn];
int par[maxn];
int tpar[maxn];

int result;

vector<int>curr_nodes;

void get_sizes(int node, int p) {
	sbt_sz[node] = 1;
	tpar[node] = p;

	for(int i:g[node]) {
		if(deleted[i] || i == p) continue;

		get_sizes(i, node);
		sbt_sz[node] += sbt_sz[i];
	}
}

void get_parents(int node, int p) {
	par[node] = p;
	curr_nodes.pb(node);
	for(int i:g[node]) {
		if(deleted[i] || i == p) continue;
		get_parents(i, node);
	}
}

int get_centroid(int node, int p, int r) {
	for(int i:g[node]) {
		if(i != p && !deleted[i] && 2*sbt_sz[i] >= sbt_sz[r]) {
			return get_centroid(i, node, r);
		}
	}
	return node;
}

void solve(int root) {
	get_sizes(root, -1); // Preprocess and find the subtree sizes of each node
	root = get_centroid(root, root, root); // Find the centroid in this tree
	get_parents(root, root);

	for(int i:curr_nodes) {
		cnt[city[i]]++;
	}

	//cout<<"Centroid: "<<root<<"\n";

	bool check = (cnt[city[root]] == sz(towns[city[root]]));
	int moves = 0;
	if(check) {
		queue<int>q;
		for(int i:towns[city[root]]) {
			q.push(i);
		}

		while(!q.empty()) {
			int curr = q.front();
			q.pop();

			//cout<<"Curr node: "<<curr<<" - "<<par[curr]<<"\n";

			if(unite(city[curr], city[par[curr]])) {
				//cout<<"merge: "<<city[curr]<<" with "<<city[par[curr]]<<"\n";
				moves++;
				check &= (cnt[city[par[curr]]] == sz(towns[city[par[curr]]]));

				if(!check) break;

				for(int i:towns[city[par[curr]]]) {
					q.push(i);
				}
			}
		}
	}

	if(check) result = min(result, moves);

	for(int i:curr_nodes) {
		usize[city[i]] = 1;
		uparent[city[i]] = city[i];
		cnt[city[i]] = 0;
	}

	curr_nodes.clear();
	deleted[root] = true;
	for(int i:g[root]) {
		if(!deleted[i]) {
			solve(i);
		}
	}
}

int main() {
	cin>>n>>k;

	int a, b;
	for(int i=0;i<n-1;i++) {
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}

	for(int i=1;i<=n;i++) {
		cin>>city[i];
		towns[city[i]].pb(i);
	}

	result = INT_MAX;
	for(int i=1;i<=k;i++) {
		usize[i] = 1;
		uparent[i] = i;
	}

	solve(1);
	cout<<result;
}

Subtask #1
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	11 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	10 ms	9728 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	10 ms	9728 KB	Output is correct
10	Correct	10 ms	9728 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	11 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	10 ms	9728 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	10 ms	9728 KB	Output is correct
10	Correct	10 ms	9728 KB	Output is correct
11	Correct	12 ms	9856 KB	Output is correct
12	Correct	13 ms	9888 KB	Output is correct
13	Correct	13 ms	9856 KB	Output is correct
14	Correct	13 ms	9856 KB	Output is correct
15	Correct	13 ms	9984 KB	Output is correct
16	Correct	13 ms	9984 KB	Output is correct
17	Correct	13 ms	9984 KB	Output is correct
18	Correct	13 ms	9984 KB	Output is correct
19	Correct	13 ms	9984 KB	Output is correct
20	Correct	13 ms	9984 KB	Output is correct
21	Correct	13 ms	9984 KB	Output is correct
22	Correct	13 ms	9984 KB	Output is correct
23	Correct	13 ms	9984 KB	Output is correct
24	Correct	13 ms	9984 KB	Output is correct
25	Correct	13 ms	9984 KB	Output is correct
26	Correct	14 ms	10112 KB	Output is correct
27	Correct	13 ms	9984 KB	Output is correct
28	Correct	13 ms	9984 KB	Output is correct
29	Correct	15 ms	9984 KB	Output is correct
30	Correct	13 ms	9984 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	812 ms	36716 KB	Output is correct
2	Correct	431 ms	40680 KB	Output is correct
3	Correct	795 ms	40172 KB	Output is correct
4	Correct	438 ms	40892 KB	Output is correct
5	Correct	790 ms	37612 KB	Output is correct
6	Correct	435 ms	40700 KB	Output is correct
7	Correct	798 ms	37880 KB	Output is correct
8	Correct	431 ms	40408 KB	Output is correct
9	Correct	893 ms	35816 KB	Output is correct
10	Correct	888 ms	33900 KB	Output is correct
11	Correct	884 ms	36072 KB	Output is correct
12	Correct	884 ms	38124 KB	Output is correct
13	Correct	879 ms	33384 KB	Output is correct
14	Correct	893 ms	38448 KB	Output is correct
15	Correct	884 ms	38320 KB	Output is correct
16	Correct	868 ms	34152 KB	Output is correct
17	Correct	889 ms	34668 KB	Output is correct
18	Correct	885 ms	34792 KB	Output is correct
19	Correct	916 ms	37352 KB	Output is correct
20	Correct	910 ms	39216 KB	Output is correct
21	Correct	10 ms	9728 KB	Output is correct

Subtask #4
59.0 / 59.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	11 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	10 ms	9728 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	10 ms	9728 KB	Output is correct
10	Correct	10 ms	9728 KB	Output is correct
11	Correct	12 ms	9856 KB	Output is correct
12	Correct	13 ms	9888 KB	Output is correct
13	Correct	13 ms	9856 KB	Output is correct
14	Correct	13 ms	9856 KB	Output is correct
15	Correct	13 ms	9984 KB	Output is correct
16	Correct	13 ms	9984 KB	Output is correct
17	Correct	13 ms	9984 KB	Output is correct
18	Correct	13 ms	9984 KB	Output is correct
19	Correct	13 ms	9984 KB	Output is correct
20	Correct	13 ms	9984 KB	Output is correct
21	Correct	13 ms	9984 KB	Output is correct
22	Correct	13 ms	9984 KB	Output is correct
23	Correct	13 ms	9984 KB	Output is correct
24	Correct	13 ms	9984 KB	Output is correct
25	Correct	13 ms	9984 KB	Output is correct
26	Correct	14 ms	10112 KB	Output is correct
27	Correct	13 ms	9984 KB	Output is correct
28	Correct	13 ms	9984 KB	Output is correct
29	Correct	15 ms	9984 KB	Output is correct
30	Correct	13 ms	9984 KB	Output is correct
31	Correct	812 ms	36716 KB	Output is correct
32	Correct	431 ms	40680 KB	Output is correct
33	Correct	795 ms	40172 KB	Output is correct
34	Correct	438 ms	40892 KB	Output is correct
35	Correct	790 ms	37612 KB	Output is correct
36	Correct	435 ms	40700 KB	Output is correct
37	Correct	798 ms	37880 KB	Output is correct
38	Correct	431 ms	40408 KB	Output is correct
39	Correct	893 ms	35816 KB	Output is correct
40	Correct	888 ms	33900 KB	Output is correct
41	Correct	884 ms	36072 KB	Output is correct
42	Correct	884 ms	38124 KB	Output is correct
43	Correct	879 ms	33384 KB	Output is correct
44	Correct	893 ms	38448 KB	Output is correct
45	Correct	884 ms	38320 KB	Output is correct
46	Correct	868 ms	34152 KB	Output is correct
47	Correct	889 ms	34668 KB	Output is correct
48	Correct	885 ms	34792 KB	Output is correct
49	Correct	916 ms	37352 KB	Output is correct
50	Correct	910 ms	39216 KB	Output is correct
51	Correct	10 ms	9728 KB	Output is correct
52	Correct	656 ms	26224 KB	Output is correct
53	Correct	680 ms	26220 KB	Output is correct
54	Correct	649 ms	26220 KB	Output is correct
55	Correct	683 ms	26220 KB	Output is correct
56	Correct	664 ms	26216 KB	Output is correct
57	Correct	625 ms	26088 KB	Output is correct
58	Correct	696 ms	29544 KB	Output is correct
59	Correct	714 ms	29768 KB	Output is correct
60	Correct	777 ms	29520 KB	Output is correct
61	Correct	758 ms	29168 KB	Output is correct
62	Correct	432 ms	40812 KB	Output is correct
63	Correct	433 ms	40812 KB	Output is correct
64	Correct	433 ms	40424 KB	Output is correct
65	Correct	432 ms	40688 KB	Output is correct
66	Correct	574 ms	33708 KB	Output is correct
67	Correct	571 ms	33320 KB	Output is correct
68	Correct	565 ms	33452 KB	Output is correct
69	Correct	582 ms	33708 KB	Output is correct
70	Correct	574 ms	33324 KB	Output is correct
71	Correct	582 ms	33452 KB	Output is correct
72	Correct	561 ms	33524 KB	Output is correct
73	Correct	569 ms	32680 KB	Output is correct
74	Correct	561 ms	33452 KB	Output is correct
75	Correct	605 ms	33720 KB	Output is correct
76	Correct	792 ms	32748 KB	Output is correct
77	Correct	781 ms	31208 KB	Output is correct
78	Correct	908 ms	34604 KB	Output is correct
79	Correct	900 ms	33132 KB	Output is correct
80	Correct	943 ms	38764 KB	Output is correct
81	Correct	974 ms	35948 KB	Output is correct
82	Correct	967 ms	35952 KB	Output is correct
83	Correct	977 ms	33384 KB	Output is correct
84	Correct	1000 ms	38120 KB	Output is correct
85	Correct	926 ms	36916 KB	Output is correct
86	Correct	899 ms	33008 KB	Output is correct
87	Correct	942 ms	34584 KB	Output is correct
88	Correct	844 ms	35420 KB	Output is correct
89	Correct	874 ms	32396 KB	Output is correct
90	Correct	855 ms	32148 KB	Output is correct
91	Correct	883 ms	33900 KB	Output is correct
92	Correct	843 ms	33072 KB	Output is correct
93	Correct	827 ms	32624 KB	Output is correct
94	Correct	831 ms	32104 KB	Output is correct
95	Correct	824 ms	33384 KB	Output is correct
96	Correct	825 ms	32264 KB	Output is correct
97	Correct	988 ms	34032 KB	Output is correct

답안 #229769

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 10.0 / 10.0

Subtask #3 30.0 / 30.0

Subtask #4 59.0 / 59.0

Subtask #1
1.0 / 1.0

Subtask #2
10.0 / 10.0

Subtask #3
30.0 / 30.0

Subtask #4
59.0 / 59.0