답안 #221460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221460	2020-04-10T08:06:00 Z	patrikpavic2	수도 (JOI20_capital_city)	C++17	100 / 100	1273 ms	37216 KB

capital_city

#include <cstdio>
#include <vector>
#include <queue>

#define PB push_back

using namespace std;

const int N = 2e5 + 500;

int sub[N], uzeo[N], C[N], cnt[N], zabr[N], par[N], centr[N], kol[N], uk[N];
int fin = N, n;
vector < int > moji, koji[N], v[N];

void dfs(int x, int lst){
	sub[x] = 1; moji.PB(x);
	par[x] = lst;
	for(int y : v[x]){
		if(centr[y] || lst == y) continue;
		dfs(y, x); sub[x] += sub[y]; 
	}
}

int nadi(int x){
	dfs(x, x);
	int nn = (int)moji.size();
	int dos = x;
	for(int y : moji){
		if(2 * sub[y] >= nn && sub[y] < sub[dos])
			dos = y;
	}
	moji.clear();
	return dos;
}

void rijesi(int x){
	dfs(x, x);
	queue < int > q; q.push(x);
	for(int y : moji) koji[C[y]].PB(y);
	for(;!q.empty();q.pop()){
		if(uzeo[q.front()])
			continue;
		int cur = q.front();
		while(!uzeo[cur]){
			if(!kol[C[cur]]){
				for(int y : koji[C[cur]])
					q.push(y);
			}
			uzeo[cur] = 1; kol[C[cur]]++;
			cur = par[cur];	
		}
	}
	for(int y : moji) koji[C[y]].clear(), uzeo[y] = 0;
	int mogu = 1, ret = 0;
	for(int y : moji){
		if(!kol[C[y]]) continue;
		if(kol[C[y]] < uk[C[y]]){
			mogu = 0; kol[C[y]] = 0;
		}
		kol[C[y]] = 0, ret++;
	}
	if(mogu)
		fin = min(fin, ret);
	moji.clear();
}

void glupost(int x){
	int cen = nadi(x);
	rijesi(cen);
	centr[cen] = 1;
	for(int y : v[cen]){
		if(!centr[y])
			glupost(y);
	}
}

int main(){
	int bla; scanf("%d%d", &n, &bla);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	for(int i = 1;i <= n;i++)
		scanf("%d", C + i), uk[C[i]]++;
	glupost(1);
	printf("%d\n", fin - 1);
	return 0;
}

Compilation message

capital_city.cpp: In function 'int main()':
capital_city.cpp:78:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int bla; scanf("%d%d", &n, &bla);
           ~~~~~^~~~~~~~~~~~~~~~~~
capital_city.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:84:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C + i), uk[C[i]]++;
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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	10 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	10 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	11 ms	9856 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	12 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	10 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	10 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	11 ms	9856 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	12 ms	9728 KB	Output is correct
10	Correct	10 ms	9728 KB	Output is correct
11	Correct	13 ms	9856 KB	Output is correct
12	Correct	13 ms	9856 KB	Output is correct
13	Correct	12 ms	9856 KB	Output is correct
14	Correct	13 ms	9856 KB	Output is correct
15	Correct	12 ms	9984 KB	Output is correct
16	Correct	13 ms	9856 KB	Output is correct
17	Correct	12 ms	9984 KB	Output is correct
18	Correct	12 ms	9984 KB	Output is correct
19	Correct	12 ms	9984 KB	Output is correct
20	Correct	13 ms	9984 KB	Output is correct
21	Correct	12 ms	9984 KB	Output is correct
22	Correct	12 ms	9984 KB	Output is correct
23	Correct	12 ms	9984 KB	Output is correct
24	Correct	14 ms	9984 KB	Output is correct
25	Correct	13 ms	10032 KB	Output is correct
26	Correct	17 ms	9984 KB	Output is correct
27	Correct	13 ms	9984 KB	Output is correct
28	Correct	13 ms	9984 KB	Output is correct
29	Correct	13 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	844 ms	36840 KB	Output is correct
2	Correct	313 ms	37216 KB	Output is correct
3	Correct	863 ms	36616 KB	Output is correct
4	Correct	309 ms	37100 KB	Output is correct
5	Correct	842 ms	34024 KB	Output is correct
6	Correct	312 ms	37112 KB	Output is correct
7	Correct	817 ms	34500 KB	Output is correct
8	Correct	323 ms	36972 KB	Output is correct
9	Correct	943 ms	32740 KB	Output is correct
10	Correct	930 ms	30700 KB	Output is correct
11	Correct	947 ms	33004 KB	Output is correct
12	Correct	943 ms	35176 KB	Output is correct
13	Correct	974 ms	30444 KB	Output is correct
14	Correct	947 ms	35376 KB	Output is correct
15	Correct	948 ms	35176 KB	Output is correct
16	Correct	975 ms	31336 KB	Output is correct
17	Correct	952 ms	31728 KB	Output is correct
18	Correct	957 ms	31796 KB	Output is correct
19	Correct	937 ms	34280 KB	Output is correct
20	Correct	930 ms	35976 KB	Output is correct
21	Correct	11 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	10 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	10 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	11 ms	9856 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	12 ms	9728 KB	Output is correct
10	Correct	10 ms	9728 KB	Output is correct
11	Correct	13 ms	9856 KB	Output is correct
12	Correct	13 ms	9856 KB	Output is correct
13	Correct	12 ms	9856 KB	Output is correct
14	Correct	13 ms	9856 KB	Output is correct
15	Correct	12 ms	9984 KB	Output is correct
16	Correct	13 ms	9856 KB	Output is correct
17	Correct	12 ms	9984 KB	Output is correct
18	Correct	12 ms	9984 KB	Output is correct
19	Correct	12 ms	9984 KB	Output is correct
20	Correct	13 ms	9984 KB	Output is correct
21	Correct	12 ms	9984 KB	Output is correct
22	Correct	12 ms	9984 KB	Output is correct
23	Correct	12 ms	9984 KB	Output is correct
24	Correct	14 ms	9984 KB	Output is correct
25	Correct	13 ms	10032 KB	Output is correct
26	Correct	17 ms	9984 KB	Output is correct
27	Correct	13 ms	9984 KB	Output is correct
28	Correct	13 ms	9984 KB	Output is correct
29	Correct	13 ms	9984 KB	Output is correct
30	Correct	13 ms	9984 KB	Output is correct
31	Correct	844 ms	36840 KB	Output is correct
32	Correct	313 ms	37216 KB	Output is correct
33	Correct	863 ms	36616 KB	Output is correct
34	Correct	309 ms	37100 KB	Output is correct
35	Correct	842 ms	34024 KB	Output is correct
36	Correct	312 ms	37112 KB	Output is correct
37	Correct	817 ms	34500 KB	Output is correct
38	Correct	323 ms	36972 KB	Output is correct
39	Correct	943 ms	32740 KB	Output is correct
40	Correct	930 ms	30700 KB	Output is correct
41	Correct	947 ms	33004 KB	Output is correct
42	Correct	943 ms	35176 KB	Output is correct
43	Correct	974 ms	30444 KB	Output is correct
44	Correct	947 ms	35376 KB	Output is correct
45	Correct	948 ms	35176 KB	Output is correct
46	Correct	975 ms	31336 KB	Output is correct
47	Correct	952 ms	31728 KB	Output is correct
48	Correct	957 ms	31796 KB	Output is correct
49	Correct	937 ms	34280 KB	Output is correct
50	Correct	930 ms	35976 KB	Output is correct
51	Correct	11 ms	9728 KB	Output is correct
52	Correct	608 ms	23272 KB	Output is correct
53	Correct	706 ms	23272 KB	Output is correct
54	Correct	673 ms	23276 KB	Output is correct
55	Correct	681 ms	23276 KB	Output is correct
56	Correct	676 ms	23272 KB	Output is correct
57	Correct	640 ms	23252 KB	Output is correct
58	Correct	656 ms	26052 KB	Output is correct
59	Correct	676 ms	26476 KB	Output is correct
60	Correct	832 ms	25964 KB	Output is correct
61	Correct	883 ms	25688 KB	Output is correct
62	Correct	310 ms	37100 KB	Output is correct
63	Correct	318 ms	37160 KB	Output is correct
64	Correct	331 ms	36912 KB	Output is correct
65	Correct	338 ms	37208 KB	Output is correct
66	Correct	637 ms	30104 KB	Output is correct
67	Correct	605 ms	29996 KB	Output is correct
68	Correct	615 ms	30072 KB	Output is correct
69	Correct	653 ms	30156 KB	Output is correct
70	Correct	655 ms	30164 KB	Output is correct
71	Correct	665 ms	31596 KB	Output is correct
72	Correct	662 ms	33384 KB	Output is correct
73	Correct	643 ms	33004 KB	Output is correct
74	Correct	722 ms	33748 KB	Output is correct
75	Correct	705 ms	33648 KB	Output is correct
76	Correct	892 ms	32736 KB	Output is correct
77	Correct	934 ms	31236 KB	Output is correct
78	Correct	1228 ms	35256 KB	Output is correct
79	Correct	1220 ms	33548 KB	Output is correct
80	Correct	1273 ms	36328 KB	Output is correct
81	Correct	1196 ms	32968 KB	Output is correct
82	Correct	1215 ms	33576 KB	Output is correct
83	Correct	1214 ms	30348 KB	Output is correct
84	Correct	1190 ms	35048 KB	Output is correct
85	Correct	1259 ms	33916 KB	Output is correct
86	Correct	1102 ms	29964 KB	Output is correct
87	Correct	1192 ms	31400 KB	Output is correct
88	Correct	1056 ms	32248 KB	Output is correct
89	Correct	1075 ms	28912 KB	Output is correct
90	Correct	1094 ms	28780 KB	Output is correct
91	Correct	1002 ms	30704 KB	Output is correct
92	Correct	1111 ms	29808 KB	Output is correct
93	Correct	1106 ms	29436 KB	Output is correct
94	Correct	1222 ms	28912 KB	Output is correct
95	Correct	1037 ms	30064 KB	Output is correct
96	Correct	994 ms	29140 KB	Output is correct
97	Correct	1030 ms	30836 KB	Output is correct

답안 #221460

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