oj.uz

Submission #1067510

# Submission time Handle Problem Language Result Execution time Memory
1067510 2024-08-20T18:56:24 Z _rain_ Cat Exercise (JOI23_ho_t4) C++14
0 / 100
 2 ms 12380 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[u]) 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] = 1 , mx[i] = 1;
	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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Incorrect 2 ms 12380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Incorrect 2 ms 12380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Incorrect 2 ms 12380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Incorrect 2 ms 12380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Incorrect 2 ms 12380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Incorrect 2 ms 12380 KB Output isn't correct
3 Halted 0 ms 0 KB -