oj.uz

Submission #1067512

# Submission time Handle Problem Language Result Execution time Memory
1067512 2024-08-20T19:01:19 Z _rain_ Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 125 ms 46420 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define debug false

const int maxn = 2e5;
const int maxlog = 20;
vector<int> g[maxn+2];
int dp[maxn+2] , p[maxn+2] , n , dep[maxn+2] , par[maxn+2][maxlog+2];

void dfs(int u , int p){
	par[u][0] = p;
	dep[u] = dep[p] + 1;
	for (int i = 1; i <= maxlog; ++i){
		par[u][i] = par[par[u][i - 1]][i - 1];
	}
	for (auto& v : g[u]){
		if (v==p) continue;
		dfs(v,u);
	}
	return;
}
int lca(int u , int v){
	if (dep[u] < dep[v]) swap(u,v);
	for (int i = maxlog; i >= 0; --i)
		if (dep[par[u][i]] >= dep[v]) u = par[u][i];
	if (u==v) return u;
	for (int i = maxlog; i >= 0; --i)
		if (par[u][i] != par[v][i]) u = par[u][i] , v = par[v][i];
	return par[u][0];
}
int dist(int u , int v){
	return dep[u] + dep[v] - 2 * dep[lca(u,v)];
}

int f[maxn+2] , sz[maxn+2] , mx[maxn+2];
int find(int u){
	return u == f[u] ? f[u] : f[u] = find(f[u]);
}
void unite(int u, int v){
	u = find(u); v = find(v);
	if (u==v) return ;
	if (sz[u] < sz[v]) swap(u,v);
	mx[u] = max(mx[u] , mx[v]);
	f[v] = u; sz[u] += sz[v];
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; ++i) sz[i] = 1 , f[i] = i , mx[i] = i;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	for (int i = 1; i < n; ++i){
		int u , v; cin >> u >> v;
		g[p[u]].push_back(p[v]);
		g[p[v]].push_back(p[u]);
	}
	dfs(n,0);
	for (int i = 1; i <= n; ++i){
		for (auto& v : g[i]){
			int x = mx[find(v)];
			if (x < i){
				dp[i] = max(dp[i] , dp[x] + dist(x , i));
				unite(x,i);
			}
		}
	}
	cout << dp[n];
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12532 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 2 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 2 ms 12376 KB Output is correct
11 Correct 2 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 2 ms 12380 KB Output is correct
14 Correct 2 ms 12380 KB Output is correct
15 Correct 2 ms 12380 KB Output is correct
16 Correct 2 ms 12380 KB Output is correct
17 Correct 2 ms 12376 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12532 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 2 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 2 ms 12376 KB Output is correct
11 Correct 2 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 2 ms 12380 KB Output is correct
14 Correct 2 ms 12380 KB Output is correct
15 Correct 2 ms 12380 KB Output is correct
16 Correct 2 ms 12380 KB Output is correct
17 Correct 2 ms 12376 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 4 ms 12892 KB Output is correct
20 Correct 4 ms 12892 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 4 ms 12780 KB Output is correct
23 Correct 4 ms 12892 KB Output is correct
24 Correct 4 ms 12784 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12532 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 2 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 2 ms 12376 KB Output is correct
11 Correct 2 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 2 ms 12380 KB Output is correct
14 Correct 2 ms 12380 KB Output is correct
15 Correct 2 ms 12380 KB Output is correct
16 Correct 2 ms 12380 KB Output is correct
17 Correct 2 ms 12376 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 4 ms 12892 KB Output is correct
20 Correct 4 ms 12892 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 4 ms 12780 KB Output is correct
23 Correct 4 ms 12892 KB Output is correct
24 Correct 4 ms 12784 KB Output is correct
25 Correct 2 ms 12380 KB Output is correct
26 Correct 4 ms 12892 KB Output is correct
27 Correct 6 ms 12892 KB Output is correct
28 Correct 4 ms 12892 KB Output is correct
29 Correct 4 ms 12892 KB Output is correct
30 Correct 4 ms 12636 KB Output is correct
31 Correct 4 ms 12788 KB Output is correct
32 Correct 4 ms 12636 KB Output is correct
33 Correct 4 ms 12636 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12532 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 2 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 2 ms 12376 KB Output is correct
11 Correct 2 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 2 ms 12380 KB Output is correct
14 Correct 2 ms 12380 KB Output is correct
15 Correct 2 ms 12380 KB Output is correct
16 Correct 2 ms 12380 KB Output is correct
17 Correct 2 ms 12376 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 4 ms 12892 KB Output is correct
20 Correct 4 ms 12892 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 4 ms 12780 KB Output is correct
23 Correct 4 ms 12892 KB Output is correct
24 Correct 4 ms 12784 KB Output is correct
25 Incorrect 92 ms 46420 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12376 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 125 ms 36748 KB Output is correct
4 Correct 111 ms 36828 KB Output is correct
5 Correct 116 ms 36856 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12532 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 2 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 2 ms 12376 KB Output is correct
11 Correct 2 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 2 ms 12380 KB Output is correct
14 Correct 2 ms 12380 KB Output is correct
15 Correct 2 ms 12380 KB Output is correct
16 Correct 2 ms 12380 KB Output is correct
17 Correct 2 ms 12376 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 4 ms 12892 KB Output is correct
20 Correct 4 ms 12892 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 4 ms 12780 KB Output is correct
23 Correct 4 ms 12892 KB Output is correct
24 Correct 4 ms 12784 KB Output is correct
25 Correct 2 ms 12380 KB Output is correct
26 Correct 4 ms 12892 KB Output is correct
27 Correct 6 ms 12892 KB Output is correct
28 Correct 4 ms 12892 KB Output is correct
29 Correct 4 ms 12892 KB Output is correct
30 Correct 4 ms 12636 KB Output is correct
31 Correct 4 ms 12788 KB Output is correct
32 Correct 4 ms 12636 KB Output is correct
33 Correct 4 ms 12636 KB Output is correct
34 Incorrect 92 ms 46420 KB Output isn't correct
35 Halted 0 ms 0 KB -