Submission #1193649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193649		pinbu	Cat Exercise (JOI23_ho_t4)	C++20	54 / 100	127 ms	44872 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 200005, L = 17;

int n, p[N], po[N];
vector<int> adj[N];
int h[N], up[N][L + 1];
void DFS(int u, int pa) {
	for (int v: adj[u]) {
		if (v == pa) {
			continue;
		}
		h[v] = h[u] + 1;
		up[v][0] = u;
		for (int k = 1; k <= L; k++) {
			up[v][k] = up[up[v][k - 1]][k - 1];
		}
		DFS(v, u);
	}
}
int LCA(int u, int v) {
	if (h[u] < h[v]) swap(u, v);
	int d = h[u] - h[v];
	for (int k = 0; k <= L; k++) {
		if ((d >> k) & 1) {
			u = up[u][k];
		}
	}
	if (u == v) {
		return u;
	}
	for (int k = L; k >= 0; k--) {
		if (up[u][k] ^ up[v][k]) {
			u = up[u][k];
			v = up[v][k];
		}
	}
	return up[u][0];
}
int dist(int u, int v) {
	return h[u] + h[v] - 2 * h[LCA(u, v)];
}

int root[N];
int find(int u) {
	return u ^ root[u] ? root[u] = find(root[u]) : u;
}

int dp[N];

void solve(void) {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
		po[p[i]] = i;
	}
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	h[1] = 0;
	DFS(1, 1);
	iota(root + 1, root + 1 + n, 1);
	
	for (int num = 1; num <= n; num++) {
		int u = po[num];
		for (int v: adj[u]) {
			if (p[v] < p[u]) {
				int rv = find(v);
				dp[u] = max(dp[u], dp[rv] + dist(u, rv));
				root[rv] = u;
			}
		}
	}
	cout << dp[po[n]];
}

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

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