Submission #1288889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288889		pvb.tunglam	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	142 ms	45836 KiB

Main

#include <bits/stdc++.h>
#define pw2(i) (1LL << (i))
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;

/*------------- I alone decide my fate ! -------------*/

int N, p[200009], id[200009];
vector <int> adj[200009];
ll dp[200009];

int parent[200009], sz[200009], ma[200009];
void make_set(int v) {
	sz[v] = 1;
	parent[v] = v;
	ma[v] = v;
}
int find(int v) {
	if (v == parent[v]) return v;
	return parent[v] = find(parent[v]);
}
void onion(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		if (sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		parent[b] = a;
		ma[a] = (p[ma[a]] > p[ma[b]] ? ma[a] : ma[b]);
	}
}

const int MAXN = 200009;
const int LOG = 20;
int up[MAXN][LOG];
int depth_arr[MAXN];

void dfs_lca(int u, int parent_node) {
	up[u][0] = parent_node;
	for (int j = 1; j < LOG; ++j) up[u][j] = up[ up[u][j-1] ][j-1];
	for (int v : adj[u]) {
		if (v == parent_node) continue;
		depth_arr[v] = depth_arr[u] + 1;
		dfs_lca(v, u);
	}
}

int lca(int a, int b) {
	if (depth_arr[a] < depth_arr[b]) swap(a, b);
	int k = depth_arr[a] - depth_arr[b];
	for (int j = 0; j < LOG; ++j) if (k & (1<<j)) a = up[a][j];
	if (a == b) return a;
	for (int j = LOG-1; j >= 0; --j) {
		if (up[a][j] != up[b][j]) {
			a = up[a][j];
			b = up[b][j];
		}
	}
	return up[a][0];
}

int dist(int a, int b) {
	int c = lca(a, b);
	return depth_arr[a] + depth_arr[b] - 2 * depth_arr[c];
}

void solve() {
	cin >> N;
	for (int i = 1; i <= N; i ++) {
		id[i] = i;
		cin >> p[i];
	}
	for (int i = 1; i < N; i ++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	depth_arr[1] = 0;
	dfs_lca(1, 1);
	sort(id + 1, id + N + 1, [] (int x, int y) {
		return p[x] < p[y];
	});
	for (int i = 1; i <= N; i ++) {
		make_set(i);
	}
	for (int i = 1; i <= N; i ++) {
		int u = id[i];
		for (auto v : adj[u]) {
			if (p[v] < p[u]) {
				dp[u] = max(dp[u], dp[ma[find(v)]] + dist(u, ma[find(v)]) );
				onion(u, v);
			}
		}
	}
	cout << dp[id[N]];
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Can't wake up? Wake me up inside
*/

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26