oj.uz

Submission #428101

# Submission time Handle Problem Language Result Execution time Memory
428101 2021-06-15T08:05:31 Z milleniumEeee Capital City (JOI20_capital_city) C++17
11 / 100
 1507 ms 32592 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;

int n, k;
vector <int> g[MAXN];
int c[MAXN];

int pr[MAXN][L + 1];
int tin[MAXN], tout[MAXN], tiktak = 0;

set <int> colors;
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;
}

struct Subtask_1_2_Solve {
	Subtask_1_2_Solve () {
		
	}
	void run() {
		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;
	}
};

struct Line_Solve {
	int l[MAXN], r[MAXN];	
	Line_Solve () {
		fill(l, l + MAXN, INF);
		fill(r, r + MAXN, -INF);
	}
	struct Point {
		int x, type;
		Point () {
			
		}
		Point (int x_, int type_) {
			x = x_, type = type_;
		}
		const bool operator < (const Point &other) {
			return x < other.x;
		}	 
	};
	void run() {
		vector <Point> vec;
		for (int i = 1; i <= n; i++) {
			chmin(l[c[i]], i);
			chmax(r[c[i]], i);
		}
		for (int i = 1; i <= k; i++) {
			vec.pb(Point(l[c[i]], 1));
			vec.pb(Point(r[c[i]], -1));
		}
		sort(all(vec));
		int cnt = 0;
		set <int> segment;
		int ans = INF;
		for (auto el : vec) {
			int x = el.x;
			int type = el.type;
			cnt += type;
			segment.insert(c[x]);
			if (cnt == 0) {
				chmin(ans, szof(segment) - 1);
				segment.clear();
			}
		}
		cout << ans << endl;
	}
};

signed main() {
	fastInp;
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		colors.insert(c[i]);
		color_comp[c[i]].pb(i);
	}
	if (n <= 2000) {
		Subtask_1_2_Solve T;
		T.run();
		return 0;
	} else {
		Line_Solve T;
		T.run();
		return 0;
	}
}

/*
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 11212 KB Output is correct
2 Correct 7 ms 11192 KB Output is correct
3 Correct 6 ms 11212 KB Output is correct
4 Correct 7 ms 11212 KB Output is correct
5 Correct 7 ms 11212 KB Output is correct
6 Correct 7 ms 11276 KB Output is correct
7 Correct 7 ms 11212 KB Output is correct
8 Correct 8 ms 11272 KB Output is correct
9 Correct 7 ms 11212 KB Output is correct
10 Correct 7 ms 11188 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11212 KB Output is correct
2 Correct 7 ms 11192 KB Output is correct
3 Correct 6 ms 11212 KB Output is correct
4 Correct 7 ms 11212 KB Output is correct
5 Correct 7 ms 11212 KB Output is correct
6 Correct 7 ms 11276 KB Output is correct
7 Correct 7 ms 11212 KB Output is correct
8 Correct 8 ms 11272 KB Output is correct
9 Correct 7 ms 11212 KB Output is correct
10 Correct 7 ms 11188 KB Output is correct
11 Correct 64 ms 11696 KB Output is correct
12 Correct 74 ms 11684 KB Output is correct
13 Correct 66 ms 11696 KB Output is correct
14 Correct 61 ms 11804 KB Output is correct
15 Correct 81 ms 11712 KB Output is correct
16 Correct 98 ms 11832 KB Output is correct
17 Correct 40 ms 11596 KB Output is correct
18 Correct 44 ms 11596 KB Output is correct
19 Correct 49 ms 11596 KB Output is correct
20 Correct 39 ms 11596 KB Output is correct
21 Correct 40 ms 11692 KB Output is correct
22 Correct 136 ms 11816 KB Output is correct
23 Correct 198 ms 11788 KB Output is correct
24 Correct 1507 ms 11712 KB Output is correct
25 Correct 87 ms 11740 KB Output is correct
26 Correct 80 ms 11748 KB Output is correct
27 Correct 92 ms 11736 KB Output is correct
28 Correct 56 ms 11724 KB Output is correct
29 Correct 59 ms 11716 KB Output is correct
30 Correct 55 ms 11672 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 32592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11212 KB Output is correct
2 Correct 7 ms 11192 KB Output is correct
3 Correct 6 ms 11212 KB Output is correct
4 Correct 7 ms 11212 KB Output is correct
5 Correct 7 ms 11212 KB Output is correct
6 Correct 7 ms 11276 KB Output is correct
7 Correct 7 ms 11212 KB Output is correct
8 Correct 8 ms 11272 KB Output is correct
9 Correct 7 ms 11212 KB Output is correct
10 Correct 7 ms 11188 KB Output is correct
11 Correct 64 ms 11696 KB Output is correct
12 Correct 74 ms 11684 KB Output is correct
13 Correct 66 ms 11696 KB Output is correct
14 Correct 61 ms 11804 KB Output is correct
15 Correct 81 ms 11712 KB Output is correct
16 Correct 98 ms 11832 KB Output is correct
17 Correct 40 ms 11596 KB Output is correct
18 Correct 44 ms 11596 KB Output is correct
19 Correct 49 ms 11596 KB Output is correct
20 Correct 39 ms 11596 KB Output is correct
21 Correct 40 ms 11692 KB Output is correct
22 Correct 136 ms 11816 KB Output is correct
23 Correct 198 ms 11788 KB Output is correct
24 Correct 1507 ms 11712 KB Output is correct
25 Correct 87 ms 11740 KB Output is correct
26 Correct 80 ms 11748 KB Output is correct
27 Correct 92 ms 11736 KB Output is correct
28 Correct 56 ms 11724 KB Output is correct
29 Correct 59 ms 11716 KB Output is correct
30 Correct 55 ms 11672 KB Output is correct
31 Incorrect 305 ms 32592 KB Output isn't correct
32 Halted 0 ms 0 KB -