oj.uz

Submission #252029

# Submission time Handle Problem Language Result Execution time Memory
252029 2020-07-23T19:21:43 Z Bruteforceman Capital City (JOI20_capital_city) C++11
100 / 100
 1720 ms 56820 KB 
#include "bits/stdc++.h"
using namespace std;
using pii = pair <int, int>;
vector <int> v[200005];
vector <int> g[200005];
int c[200005];

int disc[200005], fin[200005], dep[200005];
int anc[20][200010];
const int logn = 19;
int cur;
bool del[200005];
int n, k;

int lca(int x, int y) {
	if(dep[x] > dep[y]) {
		swap(x, y);
	}
	for(int i = logn; i >= 0; i--) {
		if(dep[y] - (1 << i) >= dep[x]) {
			y = anc[i][y];
		}
	}
	if(x == y) return x;
	for(int i = logn; i >= 0; i--) {
		if(anc[i][x] != anc[i][y]) {
			x = anc[i][x];
			y = anc[i][y];
		}
	}
	return anc[0][x];
}
void dfs(int x, int par) {
	anc[0][x] = par;
	disc[x] = ++cur;
	for(int i = 1; i <= logn; i++) {
		anc[i][x] = anc[i - 1][anc[i - 1][x]];
	}
	for(auto i : g[x]) {
		if(del[i]) continue;
		if(i - par) {
			dep[i] = 1 + dep[x];
			dfs(i, x);
		}
	}
	fin[x] = cur;
}

int par[200005];
int root(int x) {
	if(par[x] == x) return x;
	return par[x] = root(par[x]);
}
void join(int x, int y) {
	x = root(x);
	y = root(y);
	if(x != y) {
		par[x] = y;
	}
}

bool done[200005];
int ans;

int solve(int col) {
	queue <int> Q;
	set <int> cont;
	cont.insert(col);
	Q.push(col);	
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		vector <int> u = v[x];
		sort(u.begin(), u.end(), [&] (int p, int q) { return disc[p] < disc[q]; });
		for(int i = 1; i < v[x].size(); i++) {
			u.push_back(lca(u[i - 1], u[i]));
		}
		sort(u.begin(), u.end(), [&] (int p, int q) { return disc[p] < disc[q]; });
		stack <int> st;
		int last = -1;
		for(int i : u) {
			if(i == last) continue;
			while(!st.empty() && fin[st.top()] < disc[i]) {
				st.pop();
			}
			if(!st.empty()) {
				int cur = i;
				while(dep[st.top()] < dep[cur]) {
					if(done[c[cur]]) return k;
					if(!cont.count(c[cur])) Q.push(c[cur]);
					cont.insert(c[cur]);
					join(cur, anc[0][cur]);
					cur = root(anc[0][cur]);
				}
			}
			else {
				if(done[c[i]]) return k;
				if(!cont.count(c[i])) Q.push(c[i]);
				cont.insert(c[i]);
				st.push(i);
			}
			last = i; 
		}
	}
	return cont.size() - 1;
}

int sub[200010], opt[200010];
void subtree(int x, int par) {
	sub[x] = 1;
	for(auto i : g[x]) {
		if(del[i]) continue;
		if(i - par) {
			subtree(i, x);
			sub[x] += sub[i];
		}
	}
}
int centroid(int x, int par, int range) {
	for(auto i : g[x]) {
		if(del[i]) continue;
		if(i - par) {
			if(sub[i] > range) return centroid(i, x, range);
		}
	}
	return x;
}
void process(int x, int p, int root) {
	if(opt[c[x]] == -1) {
		opt[c[x]] = root;
	} else if (opt[c[x]] != root) {
		done[c[x]] = true;
	}
	for(auto i : g[x]) {
		if(del[i]) continue;
		if(i - p) {
			process(i, x, root);
		}
	}
}
void reset(int x, int p) {
	par[x] = x;
	opt[c[x]] = -1;
	for(auto i : g[x]) {
		if(del[i]) continue;
		if(i - p) {
			reset(i, x);
		}
	}
} 
void decomp(int x) {
	subtree(x, 0);
	x = centroid(x, 0, sub[x] / 2);	
	reset(x, 0);
	del[x] = true;
	if(!done[c[x]]) {
		ans = min(ans, solve(c[x]));
		done[c[x]] = true;
	}
	for(int i : g[x]) {
		if(!del[i]) {
			process(i, x, i);
		}
	}
	for(auto i : g[x]) {
		if(!del[i]) {
			decomp(i);
		}
	}
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &k);
	for(int i = 1; i < n; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].emplace_back(q);
		g[q].emplace_back(p);
	}
	for(int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
		v[c[i]].push_back(i);
	}
	dfs(1, 0);
	ans = k;
	decomp(1);
	printf("%d\n", ans);
	return 0;
}

Compilation message

capital_city.cpp: In function 'int solve(int)':
capital_city.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < v[x].size(); i++) {
                  ~~^~~~~~~~~~~~~
capital_city.cpp: In function 'int main(int, const char**)':
capital_city.cpp:174:7: 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:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:182:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9856 KB Output is correct
2 Correct 6 ms 9892 KB Output is correct
3 Correct 6 ms 9856 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 6 ms 9856 KB Output is correct
6 Correct 6 ms 9924 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9856 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 6 ms 9856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9856 KB Output is correct
2 Correct 6 ms 9892 KB Output is correct
3 Correct 6 ms 9856 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 6 ms 9856 KB Output is correct
6 Correct 6 ms 9924 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9856 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 6 ms 9856 KB Output is correct
11 Correct 9 ms 10240 KB Output is correct
12 Correct 9 ms 10240 KB Output is correct
13 Correct 9 ms 10240 KB Output is correct
14 Correct 13 ms 10240 KB Output is correct
15 Correct 9 ms 10240 KB Output is correct
16 Correct 9 ms 10240 KB Output is correct
17 Correct 8 ms 10240 KB Output is correct
18 Correct 9 ms 10240 KB Output is correct
19 Correct 9 ms 10240 KB Output is correct
20 Correct 10 ms 10240 KB Output is correct
21 Correct 8 ms 10240 KB Output is correct
22 Correct 8 ms 10368 KB Output is correct
23 Correct 11 ms 10240 KB Output is correct
24 Correct 11 ms 10240 KB Output is correct
25 Correct 10 ms 10240 KB Output is correct
26 Correct 11 ms 10368 KB Output is correct
27 Correct 9 ms 10368 KB Output is correct
28 Correct 9 ms 10240 KB Output is correct
29 Correct 9 ms 10240 KB Output is correct
30 Correct 9 ms 10240 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 56088 KB Output is correct
2 Correct 261 ms 56384 KB Output is correct
3 Correct 728 ms 55800 KB Output is correct
4 Correct 260 ms 56316 KB Output is correct
5 Correct 747 ms 53624 KB Output is correct
6 Correct 266 ms 56420 KB Output is correct
7 Correct 762 ms 54152 KB Output is correct
8 Correct 282 ms 56820 KB Output is correct
9 Correct 1108 ms 53156 KB Output is correct
10 Correct 1115 ms 51188 KB Output is correct
11 Correct 1045 ms 53576 KB Output is correct
12 Correct 1072 ms 55628 KB Output is correct
13 Correct 1038 ms 50808 KB Output is correct
14 Correct 1030 ms 55848 KB Output is correct
15 Correct 1086 ms 55672 KB Output is correct
16 Correct 1182 ms 51604 KB Output is correct
17 Correct 1024 ms 52012 KB Output is correct
18 Correct 1101 ms 52088 KB Output is correct
19 Correct 1078 ms 54648 KB Output is correct
20 Correct 1073 ms 56608 KB Output is correct
21 Correct 6 ms 9856 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9856 KB Output is correct
2 Correct 6 ms 9892 KB Output is correct
3 Correct 6 ms 9856 KB Output is correct
4 Correct 6 ms 9856 KB Output is correct
5 Correct 6 ms 9856 KB Output is correct
6 Correct 6 ms 9924 KB Output is correct
7 Correct 6 ms 9856 KB Output is correct
8 Correct 6 ms 9856 KB Output is correct
9 Correct 6 ms 9856 KB Output is correct
10 Correct 6 ms 9856 KB Output is correct
11 Correct 9 ms 10240 KB Output is correct
12 Correct 9 ms 10240 KB Output is correct
13 Correct 9 ms 10240 KB Output is correct
14 Correct 13 ms 10240 KB Output is correct
15 Correct 9 ms 10240 KB Output is correct
16 Correct 9 ms 10240 KB Output is correct
17 Correct 8 ms 10240 KB Output is correct
18 Correct 9 ms 10240 KB Output is correct
19 Correct 9 ms 10240 KB Output is correct
20 Correct 10 ms 10240 KB Output is correct
21 Correct 8 ms 10240 KB Output is correct
22 Correct 8 ms 10368 KB Output is correct
23 Correct 11 ms 10240 KB Output is correct
24 Correct 11 ms 10240 KB Output is correct
25 Correct 10 ms 10240 KB Output is correct
26 Correct 11 ms 10368 KB Output is correct
27 Correct 9 ms 10368 KB Output is correct
28 Correct 9 ms 10240 KB Output is correct
29 Correct 9 ms 10240 KB Output is correct
30 Correct 9 ms 10240 KB Output is correct
31 Correct 833 ms 56088 KB Output is correct
32 Correct 261 ms 56384 KB Output is correct
33 Correct 728 ms 55800 KB Output is correct
34 Correct 260 ms 56316 KB Output is correct
35 Correct 747 ms 53624 KB Output is correct
36 Correct 266 ms 56420 KB Output is correct
37 Correct 762 ms 54152 KB Output is correct
38 Correct 282 ms 56820 KB Output is correct
39 Correct 1108 ms 53156 KB Output is correct
40 Correct 1115 ms 51188 KB Output is correct
41 Correct 1045 ms 53576 KB Output is correct
42 Correct 1072 ms 55628 KB Output is correct
43 Correct 1038 ms 50808 KB Output is correct
44 Correct 1030 ms 55848 KB Output is correct
45 Correct 1086 ms 55672 KB Output is correct
46 Correct 1182 ms 51604 KB Output is correct
47 Correct 1024 ms 52012 KB Output is correct
48 Correct 1101 ms 52088 KB Output is correct
49 Correct 1078 ms 54648 KB Output is correct
50 Correct 1073 ms 56608 KB Output is correct
51 Correct 6 ms 9856 KB Output is correct
52 Correct 766 ms 42720 KB Output is correct
53 Correct 842 ms 42744 KB Output is correct
54 Correct 825 ms 42744 KB Output is correct
55 Correct 849 ms 42808 KB Output is correct
56 Correct 921 ms 42748 KB Output is correct
57 Correct 865 ms 42744 KB Output is correct
58 Correct 1055 ms 46048 KB Output is correct
59 Correct 927 ms 45944 KB Output is correct
60 Correct 842 ms 45432 KB Output is correct
61 Correct 957 ms 45420 KB Output is correct
62 Correct 257 ms 56440 KB Output is correct
63 Correct 260 ms 56568 KB Output is correct
64 Correct 283 ms 56624 KB Output is correct
65 Correct 270 ms 56312 KB Output is correct
66 Correct 600 ms 49788 KB Output is correct
67 Correct 504 ms 49648 KB Output is correct
68 Correct 542 ms 49896 KB Output is correct
69 Correct 521 ms 49856 KB Output is correct
70 Correct 556 ms 49812 KB Output is correct
71 Correct 632 ms 49776 KB Output is correct
72 Correct 532 ms 49652 KB Output is correct
73 Correct 516 ms 49020 KB Output is correct
74 Correct 521 ms 49776 KB Output is correct
75 Correct 526 ms 49760 KB Output is correct
76 Correct 1448 ms 49540 KB Output is correct
77 Correct 1720 ms 48264 KB Output is correct
78 Correct 1252 ms 51832 KB Output is correct
79 Correct 1092 ms 50296 KB Output is correct
80 Correct 1243 ms 56216 KB Output is correct
81 Correct 1086 ms 53240 KB Output is correct
82 Correct 1103 ms 53476 KB Output is correct
83 Correct 1108 ms 50652 KB Output is correct
84 Correct 1277 ms 55396 KB Output is correct
85 Correct 1308 ms 54100 KB Output is correct
86 Correct 1219 ms 50424 KB Output is correct
87 Correct 1194 ms 51920 KB Output is correct
88 Correct 1092 ms 52088 KB Output is correct
89 Correct 1102 ms 48888 KB Output is correct
90 Correct 1095 ms 48820 KB Output is correct
91 Correct 884 ms 50632 KB Output is correct
92 Correct 925 ms 49656 KB Output is correct
93 Correct 869 ms 49428 KB Output is correct
94 Correct 871 ms 48872 KB Output is correct
95 Correct 886 ms 50200 KB Output is correct
96 Correct 915 ms 49048 KB Output is correct
97 Correct 1109 ms 50552 KB Output is correct