oj.uz

Submission #911473

# Submission time Handle Problem Language Result Execution time Memory
911473 2024-01-19T01:44:03 Z OAleksa Capital City (JOI20_capital_city) C++14
100 / 100
 315 ms 87360 KB 
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 18;
int n, a[N], k, lca[N], vis[N];
int up[N][K], tin[N], tout[N], timer;
vector<int> g[N], t[N], rev[N], c[N];
vector<int> ord;
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int LCA(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	up[v][0] = p;
	tin[v] = ++timer;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : t[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}
void dfs1(int v) {
	if (vis[v])
		return;
	vis[v] = 1;
	for (auto u : g[v]) {
		dfs1(u);
	}
	ord.push_back(v);
}
int s[N], comp, sz[N];
vector<int> tmp;
void dfs2(int v) {
	if (vis[v])
		return;
	vis[v] = 1;
	tmp.push_back(v);
	for (auto u : rev[v]) 
		dfs2(u);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> k;
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		t[a].push_back(b);
  		t[b].push_back(a);
  	}
  	for (int i = 1;i <= n;i++) {
  		cin >> a[i];
  		c[a[i]].push_back(i);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= k;i++) {
  		assert(c[i].size() > 0);
  		lca[i] = c[i][0];
  		for (int j = 1;j < (int)c[i].size();j++)
  			lca[i] = LCA(lca[i], c[i][j]);
  	}
  	for (int i = 1;i <= n;i++) {
  		if (i == lca[a[i]])
  			continue;
  		if (a[i] != a[up[i][0]]) {
  			g[a[i]].push_back(a[up[i][0]]);
  			rev[a[up[i][0]]].push_back(a[i]);
  		}
  	}
  	for (int i = 1;i <= n;i++) {
  		sort(g[i].begin(), g[i].end());
  		g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
  		sort(rev[i].begin(), rev[i].end());
  		rev[i].erase(unique(rev[i].begin(), rev[i].end()), rev[i].end());
  	}
  	int ans = 1e9;
  	for (int i = 1;i <= k;i++) {
  		if (!vis[i])
  			dfs1(i);
  	}
  	for (int i = 1;i <= n;i++)
  		vis[i] = 0;
  	reverse(ord.begin(), ord.end());
  	for (auto u : ord) {
  		if (!vis[u]) {
  			++comp;
  			tmp.clear();
  			dfs2(u);
  			sz[comp] = (int)tmp.size();
  			for (auto x : tmp)
  				s[x] = comp;
  		}
  	}
  	for (int i = 1;i <= k;i++) {
  		int ok = 1;
  		for (auto u : g[i]) {
  			if (s[u] != s[i])
  				ok = 0;
  		}
  		if (!ok)
  			sz[s[i]] = 1e9;
  	}
  	for (int i = 1;i <= comp;i++)
  		ans = min(ans, sz[i] - 1);
  	cout << ans;
	}
  return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 7 ms 29020 KB Output is correct
4 Correct 7 ms 29020 KB Output is correct
5 Correct 7 ms 29020 KB Output is correct
6 Correct 7 ms 29116 KB Output is correct
7 Correct 8 ms 29020 KB Output is correct
8 Correct 8 ms 29020 KB Output is correct
9 Correct 7 ms 29020 KB Output is correct
10 Correct 7 ms 29104 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 9 ms 29276 KB Output is correct
13 Correct 9 ms 29276 KB Output is correct
14 Correct 8 ms 29428 KB Output is correct
15 Correct 10 ms 29276 KB Output is correct
16 Correct 9 ms 29272 KB Output is correct
17 Correct 8 ms 29276 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct
19 Correct 8 ms 29276 KB Output is correct
20 Correct 8 ms 29424 KB Output is correct
21 Correct 8 ms 29276 KB Output is correct
22 Correct 8 ms 29276 KB Output is correct
23 Correct 8 ms 29276 KB Output is correct
24 Correct 10 ms 29392 KB Output is correct
25 Correct 9 ms 29276 KB Output is correct
26 Correct 9 ms 29276 KB Output is correct
27 Correct 9 ms 29276 KB Output is correct
28 Correct 9 ms 29276 KB Output is correct
29 Correct 8 ms 29276 KB Output is correct
30 Correct 8 ms 29276 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 83252 KB Output is correct
2 Correct 107 ms 87088 KB Output is correct
3 Correct 235 ms 86684 KB Output is correct
4 Correct 108 ms 87172 KB Output is correct
5 Correct 250 ms 84244 KB Output is correct
6 Correct 108 ms 86896 KB Output is correct
7 Correct 239 ms 83820 KB Output is correct
8 Correct 106 ms 85368 KB Output is correct
9 Correct 223 ms 81100 KB Output is correct
10 Correct 224 ms 79552 KB Output is correct
11 Correct 242 ms 81356 KB Output is correct
12 Correct 248 ms 82900 KB Output is correct
13 Correct 237 ms 79572 KB Output is correct
14 Correct 236 ms 83156 KB Output is correct
15 Correct 245 ms 83148 KB Output is correct
16 Correct 249 ms 79896 KB Output is correct
17 Correct 255 ms 80416 KB Output is correct
18 Correct 226 ms 80844 KB Output is correct
19 Correct 232 ms 82696 KB Output is correct
20 Correct 262 ms 83644 KB Output is correct
21 Correct 8 ms 29020 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 7 ms 29020 KB Output is correct
4 Correct 7 ms 29020 KB Output is correct
5 Correct 7 ms 29020 KB Output is correct
6 Correct 7 ms 29116 KB Output is correct
7 Correct 8 ms 29020 KB Output is correct
8 Correct 8 ms 29020 KB Output is correct
9 Correct 7 ms 29020 KB Output is correct
10 Correct 7 ms 29104 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 9 ms 29276 KB Output is correct
13 Correct 9 ms 29276 KB Output is correct
14 Correct 8 ms 29428 KB Output is correct
15 Correct 10 ms 29276 KB Output is correct
16 Correct 9 ms 29272 KB Output is correct
17 Correct 8 ms 29276 KB Output is correct
18 Correct 8 ms 29276 KB Output is correct
19 Correct 8 ms 29276 KB Output is correct
20 Correct 8 ms 29424 KB Output is correct
21 Correct 8 ms 29276 KB Output is correct
22 Correct 8 ms 29276 KB Output is correct
23 Correct 8 ms 29276 KB Output is correct
24 Correct 10 ms 29392 KB Output is correct
25 Correct 9 ms 29276 KB Output is correct
26 Correct 9 ms 29276 KB Output is correct
27 Correct 9 ms 29276 KB Output is correct
28 Correct 9 ms 29276 KB Output is correct
29 Correct 8 ms 29276 KB Output is correct
30 Correct 8 ms 29276 KB Output is correct
31 Correct 245 ms 83252 KB Output is correct
32 Correct 107 ms 87088 KB Output is correct
33 Correct 235 ms 86684 KB Output is correct
34 Correct 108 ms 87172 KB Output is correct
35 Correct 250 ms 84244 KB Output is correct
36 Correct 108 ms 86896 KB Output is correct
37 Correct 239 ms 83820 KB Output is correct
38 Correct 106 ms 85368 KB Output is correct
39 Correct 223 ms 81100 KB Output is correct
40 Correct 224 ms 79552 KB Output is correct
41 Correct 242 ms 81356 KB Output is correct
42 Correct 248 ms 82900 KB Output is correct
43 Correct 237 ms 79572 KB Output is correct
44 Correct 236 ms 83156 KB Output is correct
45 Correct 245 ms 83148 KB Output is correct
46 Correct 249 ms 79896 KB Output is correct
47 Correct 255 ms 80416 KB Output is correct
48 Correct 226 ms 80844 KB Output is correct
49 Correct 232 ms 82696 KB Output is correct
50 Correct 262 ms 83644 KB Output is correct
51 Correct 8 ms 29020 KB Output is correct
52 Correct 233 ms 76396 KB Output is correct
53 Correct 221 ms 76424 KB Output is correct
54 Correct 247 ms 76428 KB Output is correct
55 Correct 258 ms 76424 KB Output is correct
56 Correct 234 ms 76436 KB Output is correct
57 Correct 255 ms 76396 KB Output is correct
58 Correct 238 ms 79380 KB Output is correct
59 Correct 253 ms 79820 KB Output is correct
60 Correct 272 ms 79052 KB Output is correct
61 Correct 272 ms 79104 KB Output is correct
62 Correct 120 ms 87360 KB Output is correct
63 Correct 131 ms 87240 KB Output is correct
64 Correct 104 ms 85860 KB Output is correct
65 Correct 107 ms 86920 KB Output is correct
66 Correct 201 ms 77916 KB Output is correct
67 Correct 204 ms 78024 KB Output is correct
68 Correct 199 ms 77944 KB Output is correct
69 Correct 186 ms 78024 KB Output is correct
70 Correct 177 ms 77768 KB Output is correct
71 Correct 195 ms 77972 KB Output is correct
72 Correct 205 ms 77808 KB Output is correct
73 Correct 185 ms 77488 KB Output is correct
74 Correct 183 ms 78020 KB Output is correct
75 Correct 189 ms 78024 KB Output is correct
76 Correct 264 ms 82576 KB Output is correct
77 Correct 296 ms 81488 KB Output is correct
78 Correct 246 ms 80464 KB Output is correct
79 Correct 234 ms 79092 KB Output is correct
80 Correct 226 ms 83332 KB Output is correct
81 Correct 238 ms 81032 KB Output is correct
82 Correct 245 ms 81552 KB Output is correct
83 Correct 239 ms 79388 KB Output is correct
84 Correct 232 ms 83072 KB Output is correct
85 Correct 228 ms 81836 KB Output is correct
86 Correct 243 ms 79052 KB Output is correct
87 Correct 223 ms 80132 KB Output is correct
88 Correct 268 ms 81104 KB Output is correct
89 Correct 252 ms 78532 KB Output is correct
90 Correct 284 ms 78300 KB Output is correct
91 Correct 315 ms 80236 KB Output is correct
92 Correct 276 ms 79564 KB Output is correct
93 Correct 267 ms 78784 KB Output is correct
94 Correct 292 ms 78532 KB Output is correct
95 Correct 257 ms 79556 KB Output is correct
96 Correct 276 ms 78992 KB Output is correct
97 Correct 279 ms 80072 KB Output is correct