답안 #750360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750360	2023-05-29T12:32:59 Z	Dan4Life	수도 (JOI20_capital_city)	C++17	100 / 100	2575 ms	35380 KB

capital_city

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int mxN = (int)2e5+2;

int n, m, ans = mxN;
vector<int> adj[mxN], v[mxN];
int C[mxN], sub[mxN], p[mxN], vis[mxN], vis2[mxN];

int getSub(int s, int par){
	sub[s] = 1; p[s]=par;
	for(auto u : adj[s])
		if(u!=par and !vis[u]) 
			sub[s]+=getSub(u,s);
	return sub[s];
}

int findCen(int s, int p, int n){
	for(auto u : adj[s])
		if(u!=p and !vis[u] and sub[u]>n/2)
			return findCen(u,s,n);
	return s;
}

void dfs(int s, int par, bool ok){
	p[s] = ok?par:-1;
	if(ok) vis2[C[s]]=0;
	for(auto u : adj[s])
		if(u!=par and !vis[u]) dfs(u,s,ok);
}

void cenDec(int cen, int par){
	cen = findCen(cen,par,getSub(cen,cen)); 
	dfs(cen,cen,1); vis[cen]=vis2[C[cen]]=1;
	queue<int> Q = queue<int>();
	bool ok = 1; int cnt = 0;
	for(auto u : v[C[cen]]){
		if(ok and p[u]>=0) Q.push(u);
		else ok=0;
	}
	while(!Q.empty() and ok){
		auto a = Q.front(); Q.pop();
		int CP = C[p[a]];
		if(!vis2[CP]){
			for(auto u : v[CP]){
				if(ok and p[u]>=0) Q.push(u);
				else ok=0;
			}
			if(ok) vis2[CP]=1; cnt++;
		}
	}
	if(ok) ans = min(ans, cnt);
	dfs(cen,cen,0);
	for(auto u : adj[cen])
		if(u!=par and !vis[u]) cenDec(u,cen);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m; 
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++) 
		cin >> C[i], v[C[i]].pb(i);
	cenDec(1,-1); cout << ans << "\n";
}

Compilation message

capital_city.cpp: In function 'void cenDec(int, int)':
capital_city.cpp:49:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   49 |    if(ok) vis2[CP]=1; cnt++;
      |    ^~
capital_city.cpp:49:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |    if(ok) vis2[CP]=1; cnt++;
      |                       ^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	6 ms	9724 KB	Output is correct
3	Correct	6 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	7 ms	9684 KB	Output is correct
6	Correct	6 ms	9696 KB	Output is correct
7	Correct	5 ms	9684 KB	Output is correct
8	Correct	5 ms	9744 KB	Output is correct
9	Correct	5 ms	9748 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	7 ms	9812 KB	Output is correct
12	Correct	7 ms	9812 KB	Output is correct
13	Correct	7 ms	9784 KB	Output is correct
14	Correct	8 ms	9812 KB	Output is correct
15	Correct	7 ms	9908 KB	Output is correct
16	Correct	7 ms	9812 KB	Output is correct
17	Correct	7 ms	9796 KB	Output is correct
18	Correct	6 ms	9812 KB	Output is correct
19	Correct	7 ms	9812 KB	Output is correct
20	Correct	7 ms	9932 KB	Output is correct
21	Correct	6 ms	9812 KB	Output is correct
22	Correct	7 ms	9940 KB	Output is correct
23	Correct	7 ms	9940 KB	Output is correct
24	Correct	7 ms	9812 KB	Output is correct
25	Correct	7 ms	9940 KB	Output is correct
26	Correct	8 ms	9940 KB	Output is correct
27	Correct	8 ms	9940 KB	Output is correct
28	Correct	10 ms	9940 KB	Output is correct
29	Correct	9 ms	9812 KB	Output is correct
30	Correct	8 ms	9812 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	582 ms	34856 KB	Output is correct
2	Correct	219 ms	35292 KB	Output is correct
3	Correct	622 ms	34448 KB	Output is correct
4	Correct	200 ms	35380 KB	Output is correct
5	Correct	590 ms	32064 KB	Output is correct
6	Correct	212 ms	35228 KB	Output is correct
7	Correct	747 ms	32332 KB	Output is correct
8	Correct	474 ms	34932 KB	Output is correct
9	Correct	964 ms	30836 KB	Output is correct
10	Correct	1024 ms	28780 KB	Output is correct
11	Correct	945 ms	31076 KB	Output is correct
12	Correct	916 ms	33368 KB	Output is correct
13	Correct	876 ms	28504 KB	Output is correct
14	Correct	991 ms	33576 KB	Output is correct
15	Correct	905 ms	33096 KB	Output is correct
16	Correct	988 ms	29060 KB	Output is correct
17	Correct	899 ms	29776 KB	Output is correct
18	Correct	994 ms	29828 KB	Output is correct
19	Correct	924 ms	32232 KB	Output is correct
20	Correct	1319 ms	34132 KB	Output is correct
21	Correct	6 ms	9684 KB	Output is correct

Subtask #4
59.0 / 59.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	6 ms	9724 KB	Output is correct
3	Correct	6 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	7 ms	9684 KB	Output is correct
6	Correct	6 ms	9696 KB	Output is correct
7	Correct	5 ms	9684 KB	Output is correct
8	Correct	5 ms	9744 KB	Output is correct
9	Correct	5 ms	9748 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	7 ms	9812 KB	Output is correct
12	Correct	7 ms	9812 KB	Output is correct
13	Correct	7 ms	9784 KB	Output is correct
14	Correct	8 ms	9812 KB	Output is correct
15	Correct	7 ms	9908 KB	Output is correct
16	Correct	7 ms	9812 KB	Output is correct
17	Correct	7 ms	9796 KB	Output is correct
18	Correct	6 ms	9812 KB	Output is correct
19	Correct	7 ms	9812 KB	Output is correct
20	Correct	7 ms	9932 KB	Output is correct
21	Correct	6 ms	9812 KB	Output is correct
22	Correct	7 ms	9940 KB	Output is correct
23	Correct	7 ms	9940 KB	Output is correct
24	Correct	7 ms	9812 KB	Output is correct
25	Correct	7 ms	9940 KB	Output is correct
26	Correct	8 ms	9940 KB	Output is correct
27	Correct	8 ms	9940 KB	Output is correct
28	Correct	10 ms	9940 KB	Output is correct
29	Correct	9 ms	9812 KB	Output is correct
30	Correct	8 ms	9812 KB	Output is correct
31	Correct	582 ms	34856 KB	Output is correct
32	Correct	219 ms	35292 KB	Output is correct
33	Correct	622 ms	34448 KB	Output is correct
34	Correct	200 ms	35380 KB	Output is correct
35	Correct	590 ms	32064 KB	Output is correct
36	Correct	212 ms	35228 KB	Output is correct
37	Correct	747 ms	32332 KB	Output is correct
38	Correct	474 ms	34932 KB	Output is correct
39	Correct	964 ms	30836 KB	Output is correct
40	Correct	1024 ms	28780 KB	Output is correct
41	Correct	945 ms	31076 KB	Output is correct
42	Correct	916 ms	33368 KB	Output is correct
43	Correct	876 ms	28504 KB	Output is correct
44	Correct	991 ms	33576 KB	Output is correct
45	Correct	905 ms	33096 KB	Output is correct
46	Correct	988 ms	29060 KB	Output is correct
47	Correct	899 ms	29776 KB	Output is correct
48	Correct	994 ms	29828 KB	Output is correct
49	Correct	924 ms	32232 KB	Output is correct
50	Correct	1319 ms	34132 KB	Output is correct
51	Correct	6 ms	9684 KB	Output is correct
52	Correct	509 ms	21496 KB	Output is correct
53	Correct	530 ms	21492 KB	Output is correct
54	Correct	484 ms	21500 KB	Output is correct
55	Correct	478 ms	21512 KB	Output is correct
56	Correct	503 ms	21604 KB	Output is correct
57	Correct	479 ms	21508 KB	Output is correct
58	Correct	411 ms	24064 KB	Output is correct
59	Correct	432 ms	24384 KB	Output is correct
60	Correct	509 ms	23880 KB	Output is correct
61	Correct	601 ms	23672 KB	Output is correct
62	Correct	238 ms	35092 KB	Output is correct
63	Correct	197 ms	35028 KB	Output is correct
64	Correct	365 ms	34844 KB	Output is correct
65	Correct	199 ms	35244 KB	Output is correct
66	Correct	2575 ms	28376 KB	Output is correct
67	Correct	2308 ms	28384 KB	Output is correct
68	Correct	2342 ms	28436 KB	Output is correct
69	Correct	2360 ms	28340 KB	Output is correct
70	Correct	2497 ms	28336 KB	Output is correct
71	Correct	2537 ms	28340 KB	Output is correct
72	Correct	2498 ms	28372 KB	Output is correct
73	Correct	2423 ms	27628 KB	Output is correct
74	Correct	2464 ms	28404 KB	Output is correct
75	Correct	2308 ms	28228 KB	Output is correct
76	Correct	540 ms	27280 KB	Output is correct
77	Correct	513 ms	25612 KB	Output is correct
78	Correct	792 ms	29644 KB	Output is correct
79	Correct	880 ms	27980 KB	Output is correct
80	Correct	1117 ms	33708 KB	Output is correct
81	Correct	925 ms	31052 KB	Output is correct
82	Correct	843 ms	31004 KB	Output is correct
83	Correct	915 ms	28288 KB	Output is correct
84	Correct	753 ms	32976 KB	Output is correct
85	Correct	883 ms	31696 KB	Output is correct
86	Correct	862 ms	27888 KB	Output is correct
87	Correct	923 ms	29412 KB	Output is correct
88	Correct	669 ms	30192 KB	Output is correct
89	Correct	811 ms	27072 KB	Output is correct
90	Correct	1108 ms	26968 KB	Output is correct
91	Correct	954 ms	28876 KB	Output is correct
92	Correct	698 ms	27800 KB	Output is correct
93	Correct	841 ms	27536 KB	Output is correct
94	Correct	804 ms	27072 KB	Output is correct
95	Correct	806 ms	28224 KB	Output is correct
96	Correct	686 ms	27044 KB	Output is correct
97	Correct	793 ms	28812 KB	Output is correct

답안 #750360

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