oj.uz

Submission #427966

# Submission time Handle Problem Language Result Execution time Memory
427966 2021-06-15T06:14:27 Z milleniumEeee Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 60876 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}

using namespace std;

const int MAXN  = (int)2e5 + 5;
const int INF = 1e9;
const int L = 20;

vector <int> g[MAXN];
int c[MAXN];
int pr[MAXN][L + 1];
int tin[MAXN], tout[MAXN], tiktak = 0;

vector <int> color_comp[MAXN];

void precalc(int v, int par) {
	tin[v] = ++tiktak;
	pr[v][0] = par;
	for (int lv = 1; lv <= L; lv++) {
		pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
	}
	for (int to : g[v]) {
		if (to != par) {
			precalc(to, v);
		}
	}
	tout[v] = tiktak;
}

bool father(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int get_lca(int a, int b) {
	if (father(a, b)) {
		return a;
	}
	if (father(b, a)) {
		return b;
	}
	for (int lv = L; lv >= 0; lv--) {
		if (!father(pr[a][lv], b)) {
			a = pr[a][lv];
		}
	}
	return pr[a][0];
}

int get_lca(vector <int> &vec) {
	int lca = vec[0];
	for (int i = 1; i < szof(vec); i++) {
		lca = get_lca(lca, vec[i]);
	}
	return lca;
}

int cur[MAXN];

int used[MAXN], used_id = 1;

void up_dfs(vector <int> &vec, int v, int root) {
	if (used[v] == used_id) {
		return;
	}
	used[v] = used_id;
	vec.pb(v);
	if (v != root) {
		up_dfs(vec, pr[v][0], root);		
	}	
}

void relax(vector <int> &comp) {
	used_id++;
	vector <int> res;
	int lca = get_lca(comp);
	for (int v : comp) {
		up_dfs(res, v, lca);
	}
	comp = res;
}

signed main() {
	fastInp;
	int n, k;
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	set <int> colors;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		colors.insert(c[i]);
		color_comp[c[i]].pb(i);
	}
	precalc(1, 1);
	int ans = INF;
	for (int cur_color : colors) {
		for (int i = 1; i <= n; i++) {
			cur[i] = c[i];
		}
		vector <int> comp;
		for (int i = 1; i <= n; i++) {
			if (c[i] == cur_color) {
				comp.pb(i);
			}
		}
		int cur_ans = 0;
		while (1) {
			relax(comp);
			bool ok = 1;
			set <int> new_colors;
			for (int v : comp) {
				ok &= (cur[v] == cur_color);
				if (cur[v] != cur_color) {
					new_colors.insert(cur[v]);
				}
			}
			if (ok) {
				break;
			}
			else {
				for (int el : new_colors) {
					cur_ans++;
					for (int v : color_comp[el]) {
						comp.pb(v);
						cur[v] = cur_color;
					}
				}
				continue;
			}
		}
		chmin(ans, cur_ans);
	}
	cout << ans << endl;
}

/*
12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4

*/

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 64 ms 10196 KB Output is correct
12 Correct 63 ms 10060 KB Output is correct
13 Correct 65 ms 10208 KB Output is correct
14 Correct 61 ms 10060 KB Output is correct
15 Correct 81 ms 10124 KB Output is correct
16 Correct 92 ms 10160 KB Output is correct
17 Correct 48 ms 10060 KB Output is correct
18 Correct 47 ms 10240 KB Output is correct
19 Correct 40 ms 10060 KB Output is correct
20 Correct 39 ms 10112 KB Output is correct
21 Correct 38 ms 10160 KB Output is correct
22 Correct 135 ms 10288 KB Output is correct
23 Correct 167 ms 10220 KB Output is correct
24 Correct 1453 ms 10264 KB Output is correct
25 Correct 87 ms 10060 KB Output is correct
26 Correct 78 ms 10208 KB Output is correct
27 Correct 90 ms 10172 KB Output is correct
28 Correct 52 ms 10168 KB Output is correct
29 Correct 60 ms 10168 KB Output is correct
30 Correct 53 ms 10176 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 60876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 64 ms 10196 KB Output is correct
12 Correct 63 ms 10060 KB Output is correct
13 Correct 65 ms 10208 KB Output is correct
14 Correct 61 ms 10060 KB Output is correct
15 Correct 81 ms 10124 KB Output is correct
16 Correct 92 ms 10160 KB Output is correct
17 Correct 48 ms 10060 KB Output is correct
18 Correct 47 ms 10240 KB Output is correct
19 Correct 40 ms 10060 KB Output is correct
20 Correct 39 ms 10112 KB Output is correct
21 Correct 38 ms 10160 KB Output is correct
22 Correct 135 ms 10288 KB Output is correct
23 Correct 167 ms 10220 KB Output is correct
24 Correct 1453 ms 10264 KB Output is correct
25 Correct 87 ms 10060 KB Output is correct
26 Correct 78 ms 10208 KB Output is correct
27 Correct 90 ms 10172 KB Output is correct
28 Correct 52 ms 10168 KB Output is correct
29 Correct 60 ms 10168 KB Output is correct
30 Correct 53 ms 10176 KB Output is correct
31 Execution timed out 3049 ms 60876 KB Time limit exceeded
32 Halted 0 ms 0 KB -