oj.uz

Submission #938825

# Submission time Handle Problem Language Result Execution time Memory
938825 2024-03-05T15:38:56 Z THXuan Cat Exercise (JOI23_ho_t4) C++14
100 / 100
 378 ms 122604 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e18
using namespace std;
typedef long long ll;

vector<int>adj[2000005];
ll d[2000005],par[2000005], p[2000005][25], dp[2000005];

void dfs(int s, int e) {
	for (int i = 1; i <=20; i++) {
		p[s][i] = p[p[s][i - 1]][i - 1];
	}
	for (auto u : adj[s]) {
		if (u == e) continue;
		d[u] = d[s] + 1;
		p[u][0] = s;
		dfs(u, s);
	}
}

int lca(int a, int b) {
	if (d[a] > d[b]) swap(a, b);
	int dist = d[b] - d[a];
	for (int i = 0; i <= 20; i++) {
		if (dist & (1 << i))b = p[b][i];
	}
	if (a == b) return a;
	for (int i = 20; i >= 0; i--) {
		if (p[a][i] != p[b][i]) {
			a = p[a][i];
			b = p[b][i];
		}
	}
	return p[a][0];
}

int find(int x) {
	while (x != par[x])x = par[x];
	return x;
}

int get_dist(int a, int b) {
	int lcaa = lca(a, b);
	return (d[a] - d[lcaa]) + (d[b] - d[lcaa]);
}

void solve()
{
	int n; cin >> n;
	vector<int>v(n + 1);
	for (int i = 1; i <= n; i++) cin >> v[i];
	for (int i = 1; i <= n - 1; i++) {
		int a, b; cin >> a >> b;
		a = v[a]; b = v[b];
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) par[i] = i;
	for (int i = 1; i <= n; i++) {
		for (auto u : adj[i]) {
			u = find(u);
			if (u < i) {
				par[u] = i;
				dp[i] = max(dp[i], dp[u] + get_dist(i, u));
			}
		}
	}
	cout << dp[n] << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50416 KB Output is correct
2 Correct 11 ms 50524 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50520 KB Output is correct
5 Correct 11 ms 50436 KB Output is correct
6 Correct 11 ms 50524 KB Output is correct
7 Correct 11 ms 50356 KB Output is correct
8 Correct 11 ms 50524 KB Output is correct
9 Correct 11 ms 50524 KB Output is correct
10 Correct 11 ms 50364 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50416 KB Output is correct
2 Correct 11 ms 50524 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50520 KB Output is correct
5 Correct 11 ms 50436 KB Output is correct
6 Correct 11 ms 50524 KB Output is correct
7 Correct 11 ms 50356 KB Output is correct
8 Correct 11 ms 50524 KB Output is correct
9 Correct 11 ms 50524 KB Output is correct
10 Correct 11 ms 50364 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Correct 11 ms 50524 KB Output is correct
13 Correct 13 ms 50524 KB Output is correct
14 Correct 11 ms 50520 KB Output is correct
15 Correct 12 ms 50524 KB Output is correct
16 Correct 13 ms 50676 KB Output is correct
17 Correct 11 ms 50636 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50416 KB Output is correct
2 Correct 11 ms 50524 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50520 KB Output is correct
5 Correct 11 ms 50436 KB Output is correct
6 Correct 11 ms 50524 KB Output is correct
7 Correct 11 ms 50356 KB Output is correct
8 Correct 11 ms 50524 KB Output is correct
9 Correct 11 ms 50524 KB Output is correct
10 Correct 11 ms 50364 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Correct 11 ms 50524 KB Output is correct
13 Correct 13 ms 50524 KB Output is correct
14 Correct 11 ms 50520 KB Output is correct
15 Correct 12 ms 50524 KB Output is correct
16 Correct 13 ms 50676 KB Output is correct
17 Correct 11 ms 50636 KB Output is correct
18 Correct 14 ms 53988 KB Output is correct
19 Correct 18 ms 54104 KB Output is correct
20 Correct 17 ms 54108 KB Output is correct
21 Correct 14 ms 54064 KB Output is correct
22 Correct 14 ms 54148 KB Output is correct
23 Correct 14 ms 53932 KB Output is correct
24 Correct 17 ms 54108 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50416 KB Output is correct
2 Correct 11 ms 50524 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50520 KB Output is correct
5 Correct 11 ms 50436 KB Output is correct
6 Correct 11 ms 50524 KB Output is correct
7 Correct 11 ms 50356 KB Output is correct
8 Correct 11 ms 50524 KB Output is correct
9 Correct 11 ms 50524 KB Output is correct
10 Correct 11 ms 50364 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Correct 11 ms 50524 KB Output is correct
13 Correct 13 ms 50524 KB Output is correct
14 Correct 11 ms 50520 KB Output is correct
15 Correct 12 ms 50524 KB Output is correct
16 Correct 13 ms 50676 KB Output is correct
17 Correct 11 ms 50636 KB Output is correct
18 Correct 14 ms 53988 KB Output is correct
19 Correct 18 ms 54104 KB Output is correct
20 Correct 17 ms 54108 KB Output is correct
21 Correct 14 ms 54064 KB Output is correct
22 Correct 14 ms 54148 KB Output is correct
23 Correct 14 ms 53932 KB Output is correct
24 Correct 17 ms 54108 KB Output is correct
25 Correct 12 ms 50524 KB Output is correct
26 Correct 14 ms 54108 KB Output is correct
27 Correct 16 ms 54020 KB Output is correct
28 Correct 15 ms 54108 KB Output is correct
29 Correct 17 ms 53948 KB Output is correct
30 Correct 16 ms 53724 KB Output is correct
31 Correct 14 ms 53596 KB Output is correct
32 Correct 16 ms 53848 KB Output is correct
33 Correct 16 ms 53720 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50416 KB Output is correct
2 Correct 11 ms 50524 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50520 KB Output is correct
5 Correct 11 ms 50436 KB Output is correct
6 Correct 11 ms 50524 KB Output is correct
7 Correct 11 ms 50356 KB Output is correct
8 Correct 11 ms 50524 KB Output is correct
9 Correct 11 ms 50524 KB Output is correct
10 Correct 11 ms 50364 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Correct 11 ms 50524 KB Output is correct
13 Correct 13 ms 50524 KB Output is correct
14 Correct 11 ms 50520 KB Output is correct
15 Correct 12 ms 50524 KB Output is correct
16 Correct 13 ms 50676 KB Output is correct
17 Correct 11 ms 50636 KB Output is correct
18 Correct 14 ms 53988 KB Output is correct
19 Correct 18 ms 54104 KB Output is correct
20 Correct 17 ms 54108 KB Output is correct
21 Correct 14 ms 54064 KB Output is correct
22 Correct 14 ms 54148 KB Output is correct
23 Correct 14 ms 53932 KB Output is correct
24 Correct 17 ms 54108 KB Output is correct
25 Correct 144 ms 111184 KB Output is correct
26 Correct 199 ms 122476 KB Output is correct
27 Correct 182 ms 122604 KB Output is correct
28 Correct 247 ms 121868 KB Output is correct
29 Correct 203 ms 114940 KB Output is correct
30 Correct 218 ms 120080 KB Output is correct
31 Correct 238 ms 118560 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 50520 KB Output is correct
2 Correct 13 ms 50520 KB Output is correct
3 Correct 356 ms 103252 KB Output is correct
4 Correct 378 ms 103392 KB Output is correct
5 Correct 320 ms 103336 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50416 KB Output is correct
2 Correct 11 ms 50524 KB Output is correct
3 Correct 12 ms 50524 KB Output is correct
4 Correct 12 ms 50520 KB Output is correct
5 Correct 11 ms 50436 KB Output is correct
6 Correct 11 ms 50524 KB Output is correct
7 Correct 11 ms 50356 KB Output is correct
8 Correct 11 ms 50524 KB Output is correct
9 Correct 11 ms 50524 KB Output is correct
10 Correct 11 ms 50364 KB Output is correct
11 Correct 11 ms 50520 KB Output is correct
12 Correct 11 ms 50524 KB Output is correct
13 Correct 13 ms 50524 KB Output is correct
14 Correct 11 ms 50520 KB Output is correct
15 Correct 12 ms 50524 KB Output is correct
16 Correct 13 ms 50676 KB Output is correct
17 Correct 11 ms 50636 KB Output is correct
18 Correct 14 ms 53988 KB Output is correct
19 Correct 18 ms 54104 KB Output is correct
20 Correct 17 ms 54108 KB Output is correct
21 Correct 14 ms 54064 KB Output is correct
22 Correct 14 ms 54148 KB Output is correct
23 Correct 14 ms 53932 KB Output is correct
24 Correct 17 ms 54108 KB Output is correct
25 Correct 12 ms 50524 KB Output is correct
26 Correct 14 ms 54108 KB Output is correct
27 Correct 16 ms 54020 KB Output is correct
28 Correct 15 ms 54108 KB Output is correct
29 Correct 17 ms 53948 KB Output is correct
30 Correct 16 ms 53724 KB Output is correct
31 Correct 14 ms 53596 KB Output is correct
32 Correct 16 ms 53848 KB Output is correct
33 Correct 16 ms 53720 KB Output is correct
34 Correct 144 ms 111184 KB Output is correct
35 Correct 199 ms 122476 KB Output is correct
36 Correct 182 ms 122604 KB Output is correct
37 Correct 247 ms 121868 KB Output is correct
38 Correct 203 ms 114940 KB Output is correct
39 Correct 218 ms 120080 KB Output is correct
40 Correct 238 ms 118560 KB Output is correct
41 Correct 11 ms 50520 KB Output is correct
42 Correct 13 ms 50520 KB Output is correct
43 Correct 356 ms 103252 KB Output is correct
44 Correct 378 ms 103392 KB Output is correct
45 Correct 320 ms 103336 KB Output is correct
46 Correct 293 ms 118036 KB Output is correct
47 Correct 288 ms 117904 KB Output is correct
48 Correct 286 ms 117968 KB Output is correct
49 Correct 305 ms 118032 KB Output is correct
50 Correct 262 ms 107092 KB Output is correct
51 Correct 249 ms 107516 KB Output is correct
52 Correct 297 ms 107088 KB Output is correct
53 Correct 223 ms 107272 KB Output is correct