oj.uz

Submission #242097

# Submission time Handle Problem Language Result Execution time Memory
242097 2020-06-26T19:08:37 Z ZwariowanyMarcin Capital City (JOI20_capital_city) C++14
100 / 100
 963 ms 39660 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
 
using namespace std;

const int N = 2e5 + 101;

int n, k, a, b, res = 1e9;
vector <int> g[N], x;
bool dead[N], vis[N];
int siz[N], color[N], total[N], par[N], last[N], id;
vector <int> q[N];

void licz(int v, int p) {
	siz[v] = 1;
	for (auto it : g[v])
		if (!dead[it] && it != p) {
			licz(it, v);
			siz[v] += siz[it];
		}
}

int daj(int v, int p, int all) {
	for (auto it : g[v])
		if (!dead[it] && it != p && all < 2 * siz[it])
			return daj(it, v, all);
	return v;
}

void dfs(int v, int p) {
	x.pb(v);
	q[color[v]].pb(v);
	par[v] = p;
	for (auto it : g[v])
		if (!dead[it] && it != p)
			dfs(it, v);
}

vector <int> stos;
bool bad;
int now;

void add(int c) {
	if (last[c] == id) return;
	if (total[c] != ss(q[c])) bad = true;
	last[c] = id;
	now++;
	stos.pb(c);
}

void dek(int v) {
	licz(v, 0);
	int cen = daj(v, 0, siz[v]);
	// process cen
	dfs(cen, 0);
	++id;
	bad = false;
	now = 0;
	add(color[cen]);
	while (!stos.empty()) {
		int k = stos.back();
		stos.pop_back();
		for (auto it : q[k]) {
			int s = it;
			while (s != 0 && !vis[s]) {
				vis[s] = true;
				add(color[s]);
				s = par[s];
			}
		}
	}
	if (!bad) res = min(res, now);
	for (auto it : x) {
		q[color[it]].clear();
		vis[it] = false;
	}
	x.clear();
	dead[cen] = true;
	for (auto it : g[cen])
		if (!dead[it])
			dek(it);
	
}

int main() {
	scanf ("%d%d", &n, &k);
	rep(i, 2, n) {
		scanf ("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	rep(i, 1, n) {
		scanf ("%d", color + i);
		total[color[i]]++;
	}
	dek(1);
	printf ("%d\n", res - 1);
	return 0;
}

Compilation message

capital_city.cpp: In function 'int main()':
capital_city.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &k);
  ~~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", color + i);
   ~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 11 ms 9728 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 10 ms 9856 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

# Verdict Execution time Memory Grader output
1 Correct 11 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 11 ms 9728 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 10 ms 9856 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 12 ms 9856 KB Output is correct
13 Correct 13 ms 9856 KB Output is correct
14 Correct 12 ms 9856 KB Output is correct
15 Correct 12 ms 9984 KB Output is correct
16 Correct 12 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 12 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 12 ms 9984 KB Output is correct
25 Correct 12 ms 9984 KB Output is correct
26 Correct 13 ms 9984 KB Output is correct
27 Correct 13 ms 9984 KB Output is correct
28 Correct 12 ms 9984 KB Output is correct
29 Correct 12 ms 9984 KB Output is correct
30 Correct 14 ms 9984 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 39300 KB Output is correct
2 Correct 273 ms 39656 KB Output is correct
3 Correct 919 ms 39148 KB Output is correct
4 Correct 272 ms 39656 KB Output is correct
5 Correct 829 ms 36584 KB Output is correct
6 Correct 273 ms 39528 KB Output is correct
7 Correct 836 ms 36844 KB Output is correct
8 Correct 277 ms 39304 KB Output is correct
9 Correct 904 ms 35052 KB Output is correct
10 Correct 909 ms 33060 KB Output is correct
11 Correct 906 ms 35308 KB Output is correct
12 Correct 884 ms 37608 KB Output is correct
13 Correct 863 ms 32748 KB Output is correct
14 Correct 873 ms 37740 KB Output is correct
15 Correct 918 ms 37620 KB Output is correct
16 Correct 876 ms 33596 KB Output is correct
17 Correct 871 ms 34004 KB Output is correct
18 Correct 886 ms 34160 KB Output is correct
19 Correct 880 ms 36484 KB Output is correct
20 Correct 884 ms 38248 KB Output is correct
21 Correct 10 ms 9728 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 11 ms 9728 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 10 ms 9856 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 12 ms 9856 KB Output is correct
13 Correct 13 ms 9856 KB Output is correct
14 Correct 12 ms 9856 KB Output is correct
15 Correct 12 ms 9984 KB Output is correct
16 Correct 12 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 12 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 12 ms 9984 KB Output is correct
25 Correct 12 ms 9984 KB Output is correct
26 Correct 13 ms 9984 KB Output is correct
27 Correct 13 ms 9984 KB Output is correct
28 Correct 12 ms 9984 KB Output is correct
29 Correct 12 ms 9984 KB Output is correct
30 Correct 14 ms 9984 KB Output is correct
31 Correct 842 ms 39300 KB Output is correct
32 Correct 273 ms 39656 KB Output is correct
33 Correct 919 ms 39148 KB Output is correct
34 Correct 272 ms 39656 KB Output is correct
35 Correct 829 ms 36584 KB Output is correct
36 Correct 273 ms 39528 KB Output is correct
37 Correct 836 ms 36844 KB Output is correct
38 Correct 277 ms 39304 KB Output is correct
39 Correct 904 ms 35052 KB Output is correct
40 Correct 909 ms 33060 KB Output is correct
41 Correct 906 ms 35308 KB Output is correct
42 Correct 884 ms 37608 KB Output is correct
43 Correct 863 ms 32748 KB Output is correct
44 Correct 873 ms 37740 KB Output is correct
45 Correct 918 ms 37620 KB Output is correct
46 Correct 876 ms 33596 KB Output is correct
47 Correct 871 ms 34004 KB Output is correct
48 Correct 886 ms 34160 KB Output is correct
49 Correct 880 ms 36484 KB Output is correct
50 Correct 884 ms 38248 KB Output is correct
51 Correct 10 ms 9728 KB Output is correct
52 Correct 561 ms 25064 KB Output is correct
53 Correct 615 ms 25068 KB Output is correct
54 Correct 648 ms 25064 KB Output is correct
55 Correct 663 ms 25068 KB Output is correct
56 Correct 609 ms 25068 KB Output is correct
57 Correct 574 ms 25196 KB Output is correct
58 Correct 629 ms 28648 KB Output is correct
59 Correct 559 ms 28908 KB Output is correct
60 Correct 736 ms 28396 KB Output is correct
61 Correct 772 ms 28136 KB Output is correct
62 Correct 265 ms 39640 KB Output is correct
63 Correct 265 ms 39660 KB Output is correct
64 Correct 271 ms 39276 KB Output is correct
65 Correct 266 ms 39656 KB Output is correct
66 Correct 488 ms 32620 KB Output is correct
67 Correct 452 ms 32604 KB Output is correct
68 Correct 456 ms 32620 KB Output is correct
69 Correct 435 ms 32620 KB Output is correct
70 Correct 449 ms 32620 KB Output is correct
71 Correct 434 ms 32492 KB Output is correct
72 Correct 474 ms 32496 KB Output is correct
73 Correct 450 ms 31852 KB Output is correct
74 Correct 466 ms 32752 KB Output is correct
75 Correct 449 ms 32632 KB Output is correct
76 Correct 677 ms 31592 KB Output is correct
77 Correct 699 ms 30316 KB Output is correct
78 Correct 872 ms 33900 KB Output is correct
79 Correct 885 ms 32336 KB Output is correct
80 Correct 881 ms 38140 KB Output is correct
81 Correct 877 ms 35308 KB Output is correct
82 Correct 890 ms 35388 KB Output is correct
83 Correct 870 ms 32492 KB Output is correct
84 Correct 959 ms 37356 KB Output is correct
85 Correct 907 ms 36200 KB Output is correct
86 Correct 920 ms 32232 KB Output is correct
87 Correct 963 ms 33644 KB Output is correct
88 Correct 836 ms 34540 KB Output is correct
89 Correct 814 ms 31252 KB Output is correct
90 Correct 828 ms 31112 KB Output is correct
91 Correct 846 ms 33004 KB Output is correct
92 Correct 837 ms 31848 KB Output is correct
93 Correct 873 ms 31728 KB Output is correct
94 Correct 880 ms 31220 KB Output is correct
95 Correct 810 ms 32364 KB Output is correct
96 Correct 856 ms 31340 KB Output is correct
97 Correct 876 ms 32928 KB Output is correct