oj.uz

Submission #932924

# Submission time Handle Problem Language Result Execution time Memory
932924 2024-02-24T14:27:44 Z ParsaS Capital City (JOI20_capital_city) C++17
31 / 100
 230 ms 96840 KB 
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4e5 + 5, lg = 20;
int n, k;
int up[N][lg], f[N], c[N];
vector<int> adj[N], ver[N];
int h[N], tin[N], tout[N], T;
int par[N];

void dfs(int v, int p) {
	par[v] = p;
	up[v][0] = p;
	for (int i = 1; i < lg; i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	tin[v] = ++T;
	for (auto u : adj[v]) {
		if (u != p) {
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
	tout[v] = T;
}

bool anc(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int v, int u) {
	if (tin[v] > tin[u]) swap(v, u);
	if (anc(v, u)) return v;
	for (int i = lg - 1; i >= 0; i--)
		if (!anc(up[u][i], v))
			u = up[u][i];
	return up[u][0];

}
vector<int> out[N], in[N];
int CNT = 0;

void dfs2(int v, int p) {
	int u = par[v];
	while (h[u] > h[f[c[v]]]) {
		out[c[v]].pb(c[u]);
		in[c[u]].pb(c[v]);

		CNT++;
		assert(CNT <= n * 3);
		u = par[u];
	}
	par[v] = u;
	if (h[u] >= h[f[c[v]]]) {
		out[c[v]].pb(c[f[c[v]]]);
		in[c[f[c[v]]]].pb(c[v]);


		par[v] = par[f[c[v]]];
	}
	for (auto u : adj[v]) {
		if (u != p)
			dfs2(u, v);
	}
}
bool vis[N];
int col[N];
vector<int> vec;

void dfs3(int v) {
	vis[v] = true;
	for (auto u : out[v]) {
		if (!vis[u]) dfs3(u);
	}
	vec.pb(v);
}
vector<int> V;

void dfs4(int v, int x) {
	col[v] = x;
	for (auto u : in[v]) {
		if (!col[u])
			dfs4(u, x);
	}
	V.pb(v);
}

void solve() {
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++) {
		int v, u; cin >> v >> u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	for (int i = 1; i <= n; i++) cin >> c[i], ver[c[i]].pb(i);

	dfs(1, 0);
	h[0] = -1;
	tout[0] = T;

	for (int i = 1; i <= k; i++) {
		f[i] = ver[i].back();
		for (auto v : ver[i])
			f[i] = lca(f[i], v);
	}

	dfs2(1, 0);
	for (int i = 1; i <= k; i++) {
		if (!vis[i])
			dfs3(i);
	}
	int ans = n + 1;
	for (int i = k - 1; i >= 0; i--) {
		int w = vec[i];
		if (col[w] == 0) {
			V.clear();
			dfs4(w, w);
			bool ok = true;
			int cnt = V.size();
			for (auto v : V) {
				for (auto u : out[v])
					ok &= col[u] == col[v];
			}
			if (ok) ans = min(ans, cnt);	
		}
	}
	cout << ans - 1 << '\n';

}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc = 1; // cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47452 KB Output is correct
2 Correct 10 ms 47448 KB Output is correct
3 Correct 11 ms 47452 KB Output is correct
4 Correct 9 ms 47452 KB Output is correct
5 Correct 10 ms 47452 KB Output is correct
6 Correct 10 ms 47452 KB Output is correct
7 Correct 9 ms 47452 KB Output is correct
8 Correct 9 ms 47600 KB Output is correct
9 Correct 10 ms 47452 KB Output is correct
10 Correct 10 ms 49640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47452 KB Output is correct
2 Correct 10 ms 47448 KB Output is correct
3 Correct 11 ms 47452 KB Output is correct
4 Correct 9 ms 47452 KB Output is correct
5 Correct 10 ms 47452 KB Output is correct
6 Correct 10 ms 47452 KB Output is correct
7 Correct 9 ms 47452 KB Output is correct
8 Correct 9 ms 47600 KB Output is correct
9 Correct 10 ms 47452 KB Output is correct
10 Correct 10 ms 49640 KB Output is correct
11 Correct 11 ms 47960 KB Output is correct
12 Correct 11 ms 47708 KB Output is correct
13 Correct 10 ms 47704 KB Output is correct
14 Correct 11 ms 47708 KB Output is correct
15 Correct 11 ms 47708 KB Output is correct
16 Runtime error 45 ms 96492 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 96204 KB Output is correct
2 Correct 130 ms 96716 KB Output is correct
3 Correct 205 ms 95948 KB Output is correct
4 Correct 109 ms 96840 KB Output is correct
5 Correct 230 ms 92636 KB Output is correct
6 Correct 111 ms 96732 KB Output is correct
7 Correct 209 ms 92496 KB Output is correct
8 Correct 123 ms 95600 KB Output is correct
9 Correct 201 ms 89300 KB Output is correct
10 Correct 198 ms 86912 KB Output is correct
11 Correct 221 ms 89768 KB Output is correct
12 Correct 202 ms 92364 KB Output is correct
13 Correct 212 ms 86492 KB Output is correct
14 Correct 205 ms 92636 KB Output is correct
15 Correct 204 ms 92376 KB Output is correct
16 Correct 190 ms 87312 KB Output is correct
17 Correct 210 ms 88024 KB Output is correct
18 Correct 192 ms 88288 KB Output is correct
19 Correct 199 ms 91460 KB Output is correct
20 Correct 209 ms 93644 KB Output is correct
21 Correct 10 ms 49500 KB Output is correct

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47452 KB Output is correct
2 Correct 10 ms 47448 KB Output is correct
3 Correct 11 ms 47452 KB Output is correct
4 Correct 9 ms 47452 KB Output is correct
5 Correct 10 ms 47452 KB Output is correct
6 Correct 10 ms 47452 KB Output is correct
7 Correct 9 ms 47452 KB Output is correct
8 Correct 9 ms 47600 KB Output is correct
9 Correct 10 ms 47452 KB Output is correct
10 Correct 10 ms 49640 KB Output is correct
11 Correct 11 ms 47960 KB Output is correct
12 Correct 11 ms 47708 KB Output is correct
13 Correct 10 ms 47704 KB Output is correct
14 Correct 11 ms 47708 KB Output is correct
15 Correct 11 ms 47708 KB Output is correct
16 Runtime error 45 ms 96492 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -