답안 #262604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262604	2020-08-13T05:11:22 Z	dennisstar	수도 (JOI20_capital_city)	C++17	11 / 100	1581 ms	524292 KB

capital_city

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

const int MX = 2e5 + 5;

int N, K, C[MX];
int A, vis[MX], sz[MX];
vector<int> adj[MX], ele[MX];

int P[MX], cnt[MX], use[MX], clh[MX];
void d1(int n, int p) {
	sz[n]=1; cnt[C[n]]++;
	for (auto &i:adj[n])
		if (i!=p&&!vis[i]) d1(i, n), sz[n]+=sz[i];
}

int d2(int n, int p, int c) {
	for (auto &i:adj[n])
		if (i!=p&&!vis[i]&&sz[i]>=c) return d2(i, n, c);
	return n;
}

void d3(int n, int p) {
	P[n]=p;
	for (auto &i:adj[n])
		if (i!=p&&!vis[i]) d3(i, n);
}

void d4(int n, int p) {
	cnt[C[n]]=0;
	for (auto &i:adj[n])
		if (i!=p&&!vis[i]) d4(i, n);
}

void sol(int st) {
	d1(st, 0);
	int c=d2(st, 0, sz[st]/2+1);
	d3(c, 0);

	int fl=0, d=0;
	vector<int> s; s.eb(c);
	for (int i=0; i<s.size(); i++) {
		int x=s[i];
		if (use[x]) continue;
		if (ele[C[x]].size()!=cnt[C[x]]) { fl=1; break; }
		if (!clh[C[x]]) {
			clh[C[x]]=1;
			d++;
			for (auto &j:ele[C[x]]) s.eb(j);
		}
		if (P[x]) s.eb(P[x]);
	}
	if (!fl) A=min(A, d);
	for (auto &i:s) use[i]=0, clh[C[i]]=0;
	d4(st, 0);

	vis[c]=1;
	for (auto &i:adj[c]) if (!vis[i]) sol(i);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin>>N>>K;
	for (int i=1, u, v; i<N; i++) cin>>u>>v, adj[u].eb(v), adj[v].eb(u);
	for (int i=1; i<=N; i++) cin>>C[i], ele[C[i]].eb(i);

	A=MX;
	sol(1);

	cout<<A-1<<'\n';
	return 0;
}

Compilation message

capital_city.cpp: In function 'void sol(int)':
capital_city.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i=0; i<s.size(); i++) {
      |                ~^~~~~~~~~
capital_city.cpp:46:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |   if (ele[C[x]].size()!=cnt[C[x]]) { fl=1; break; }
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	729 ms	36704 KB	Output is correct
2	Correct	241 ms	36856 KB	Output is correct
3	Correct	688 ms	36472 KB	Output is correct
4	Correct	233 ms	36856 KB	Output is correct
5	Runtime error	1581 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 59.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	9728 KB	Output is correct
2	Correct	7 ms	9856 KB	Output is correct
3	Correct	8 ms	9728 KB	Output is correct
4	Correct	9 ms	9728 KB	Output is correct
5	Correct	8 ms	9728 KB	Output is correct
6	Correct	7 ms	9856 KB	Output is correct
7	Correct	7 ms	9728 KB	Output is correct
8	Correct	7 ms	9728 KB	Output is correct
9	Correct	7 ms	9728 KB	Output is correct
10	Correct	7 ms	9728 KB	Output is correct
11	Correct	9 ms	10056 KB	Output is correct
12	Correct	10 ms	9984 KB	Output is correct
13	Correct	9 ms	10112 KB	Output is correct
14	Correct	9 ms	9984 KB	Output is correct
15	Correct	11 ms	9984 KB	Output is correct
16	Correct	9 ms	10112 KB	Output is correct
17	Correct	15 ms	12148 KB	Output is correct
18	Correct	15 ms	12148 KB	Output is correct
19	Correct	15 ms	12148 KB	Output is correct
20	Correct	15 ms	12148 KB	Output is correct
21	Correct	15 ms	12148 KB	Output is correct
22	Correct	8 ms	9984 KB	Output is correct
23	Correct	9 ms	9984 KB	Output is correct
24	Correct	13 ms	10744 KB	Output is correct
25	Correct	23 ms	13808 KB	Output is correct
26	Correct	24 ms	13932 KB	Output is correct
27	Correct	24 ms	13936 KB	Output is correct
28	Correct	20 ms	12148 KB	Output is correct
29	Correct	17 ms	12148 KB	Output is correct
30	Correct	19 ms	12656 KB	Output is correct
31	Correct	729 ms	36704 KB	Output is correct
32	Correct	241 ms	36856 KB	Output is correct
33	Correct	688 ms	36472 KB	Output is correct
34	Correct	233 ms	36856 KB	Output is correct
35	Runtime error	1581 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Halted	0 ms	0 KB	-

답안 #262604

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 30.0

Subtask #4 0 / 59.0

Subtask #1
1.0 / 1.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 30.0

Subtask #4
0 / 59.0