답안 #924063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924063	2024-02-08T10:52:49 Z	KiaRez	수도 (JOI20_capital_city)	C++17	100 / 100	636 ms	43044 KB

capital_city

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 2e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, k, ans, glob, par[N], cnt[N], vis[N], c[N], sz[N], mark[N];
vector<int> adj[N], g[N];

void init(int v, int p=0, int f=0) {
	if(f==1) cnt[c[v]] ++;
	sz[v] = 1;
	par[v] = p;
	for(int u : adj[v]) {
		if(u == p || mark[u] == 1) continue;
		init(u, v, f);
		sz[v] += sz[u];
	}
}

int findC(int v, int p=0) {
	int res=-1, yey=(glob-sz[v] <= glob/2 ? 1 : 0);
	for(int u : adj[v]) {
		if(u == p || mark[u] == 1) continue;
		res = max(res, findC(u, v));
		yey &= (sz[u] <= glob/2);
	}
	if(yey==1) res = v;
	return res;
}

void clen(int v, int p=0) {
	cnt[c[v]] = 0, par[v] = 0, sz[v] = 0;
	vis[c[v]] = 0;
	for(int u : adj[v]) {
		if(u == p || mark[u] == 1) continue;
		clen(u, v);
	}
}

void calc(int v) {
	init(v);
	glob = sz[v];
	v = findC(v);
	init(v, 0, 1);
	
	int res = 0;
	queue<int> q;
	q.push(c[v]);
	vis[c[v]] = 1;
	while(size(q) > 0) {
		int col = q.front();
		q.pop();
		if(cnt[col] < size(g[col])) {
			res = k-1;
			break;
		}
		for(auto u : g[col]) {
			if(par[u]!=0 && vis[c[par[u]]]==0) {
				vis[c[par[u]]] = 1;
				q.push(c[par[u]]);
				res++;
			}
		}
	}
	clen(v);
	mark[v]=1;
	ans = min(ans, res);
	for(int u : adj[v]) {
		if(mark[u] == 0) {
			calc(u);
		}
	}
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>k; ans = k-1;
	for(int v,u,i=1; i<n; i++) {
		cin>>v>>u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	for(int i=1; i<=n; i++) {
		cin>>c[i];
		g[c[i]].pb(i);
	}

	calc(1);

	cout<<ans<<endl;

	return 0;
}

Subtask #1

1.0 / 1.0

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

Subtask #2

10.0 / 10.0

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

Subtask #3

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	432 ms	42172 KB	Output is correct
2	Correct	207 ms	42832 KB	Output is correct
3	Correct	432 ms	41808 KB	Output is correct
4	Correct	186 ms	42840 KB	Output is correct
5	Correct	401 ms	38892 KB	Output is correct
6	Correct	184 ms	42796 KB	Output is correct
7	Correct	354 ms	39252 KB	Output is correct
8	Correct	180 ms	42228 KB	Output is correct
9	Correct	564 ms	37204 KB	Output is correct
10	Correct	481 ms	34968 KB	Output is correct
11	Correct	540 ms	37944 KB	Output is correct
12	Correct	568 ms	40484 KB	Output is correct
13	Correct	494 ms	34536 KB	Output is correct
14	Correct	508 ms	40680 KB	Output is correct
15	Correct	521 ms	40752 KB	Output is correct
16	Correct	458 ms	35408 KB	Output is correct
17	Correct	593 ms	36112 KB	Output is correct
18	Correct	553 ms	36272 KB	Output is correct
19	Correct	488 ms	39404 KB	Output is correct
20	Correct	502 ms	41676 KB	Output is correct
21	Correct	4 ms	12888 KB	Output is correct

Subtask #4

59.0 / 59.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12892 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	4 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	3 ms	12892 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	4 ms	12892 KB	Output is correct
12	Correct	8 ms	12892 KB	Output is correct
13	Correct	5 ms	12888 KB	Output is correct
14	Correct	6 ms	13148 KB	Output is correct
15	Correct	4 ms	12892 KB	Output is correct
16	Correct	4 ms	12892 KB	Output is correct
17	Correct	4 ms	13148 KB	Output is correct
18	Correct	5 ms	13148 KB	Output is correct
19	Correct	4 ms	13148 KB	Output is correct
20	Correct	4 ms	13148 KB	Output is correct
21	Correct	4 ms	12980 KB	Output is correct
22	Correct	5 ms	13144 KB	Output is correct
23	Correct	4 ms	13148 KB	Output is correct
24	Correct	4 ms	13144 KB	Output is correct
25	Correct	4 ms	13144 KB	Output is correct
26	Correct	5 ms	13144 KB	Output is correct
27	Correct	4 ms	13148 KB	Output is correct
28	Correct	4 ms	13148 KB	Output is correct
29	Correct	4 ms	13148 KB	Output is correct
30	Correct	4 ms	13148 KB	Output is correct
31	Correct	432 ms	42172 KB	Output is correct
32	Correct	207 ms	42832 KB	Output is correct
33	Correct	432 ms	41808 KB	Output is correct
34	Correct	186 ms	42840 KB	Output is correct
35	Correct	401 ms	38892 KB	Output is correct
36	Correct	184 ms	42796 KB	Output is correct
37	Correct	354 ms	39252 KB	Output is correct
38	Correct	180 ms	42228 KB	Output is correct
39	Correct	564 ms	37204 KB	Output is correct
40	Correct	481 ms	34968 KB	Output is correct
41	Correct	540 ms	37944 KB	Output is correct
42	Correct	568 ms	40484 KB	Output is correct
43	Correct	494 ms	34536 KB	Output is correct
44	Correct	508 ms	40680 KB	Output is correct
45	Correct	521 ms	40752 KB	Output is correct
46	Correct	458 ms	35408 KB	Output is correct
47	Correct	593 ms	36112 KB	Output is correct
48	Correct	553 ms	36272 KB	Output is correct
49	Correct	488 ms	39404 KB	Output is correct
50	Correct	502 ms	41676 KB	Output is correct
51	Correct	4 ms	12888 KB	Output is correct
52	Correct	258 ms	25356 KB	Output is correct
53	Correct	315 ms	25436 KB	Output is correct
54	Correct	340 ms	25316 KB	Output is correct
55	Correct	354 ms	25352 KB	Output is correct
56	Correct	339 ms	25216 KB	Output is correct
57	Correct	340 ms	25168 KB	Output is correct
58	Correct	290 ms	29220 KB	Output is correct
59	Correct	258 ms	29520 KB	Output is correct
60	Correct	319 ms	28868 KB	Output is correct
61	Correct	373 ms	28516 KB	Output is correct
62	Correct	173 ms	42788 KB	Output is correct
63	Correct	177 ms	42832 KB	Output is correct
64	Correct	174 ms	42436 KB	Output is correct
65	Correct	196 ms	43044 KB	Output is correct
66	Correct	244 ms	34168 KB	Output is correct
67	Correct	235 ms	34036 KB	Output is correct
68	Correct	269 ms	34148 KB	Output is correct
69	Correct	315 ms	34160 KB	Output is correct
70	Correct	248 ms	34012 KB	Output is correct
71	Correct	231 ms	34068 KB	Output is correct
72	Correct	244 ms	34004 KB	Output is correct
73	Correct	263 ms	33260 KB	Output is correct
74	Correct	295 ms	34176 KB	Output is correct
75	Correct	235 ms	33920 KB	Output is correct
76	Correct	339 ms	32848 KB	Output is correct
77	Correct	325 ms	30984 KB	Output is correct
78	Correct	495 ms	35924 KB	Output is correct
79	Correct	511 ms	33956 KB	Output is correct
80	Correct	636 ms	41200 KB	Output is correct
81	Correct	499 ms	37576 KB	Output is correct
82	Correct	571 ms	37724 KB	Output is correct
83	Correct	521 ms	34644 KB	Output is correct
84	Correct	516 ms	40276 KB	Output is correct
85	Correct	554 ms	38652 KB	Output is correct
86	Correct	501 ms	33908 KB	Output is correct
87	Correct	568 ms	35708 KB	Output is correct
88	Correct	463 ms	36620 KB	Output is correct
89	Correct	432 ms	32836 KB	Output is correct
90	Correct	416 ms	32680 KB	Output is correct
91	Correct	476 ms	35152 KB	Output is correct
92	Correct	408 ms	33876 KB	Output is correct
93	Correct	388 ms	33368 KB	Output is correct
94	Correct	451 ms	32908 KB	Output is correct
95	Correct	442 ms	34128 KB	Output is correct
96	Correct	406 ms	32792 KB	Output is correct
97	Correct	395 ms	35040 KB	Output is correct