Submission #763839

#	Time	Username	Problem	Language	Result	Execution time	Memory
763839		NK_	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	367 ms	70580 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

struct DSU {
	vector<int> e, mx; void init(int N, const vector<int>& A) { e = vector<int>(N, -1); mx = A; }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	int getmx(int x) { return mx[get(x)]; }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; mx[x] = max(mx[x], mx[y]); e[y] = x; return 1;
	}
};

using ll = long long;

const int LG = 20;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	vector<int> A(N); for(auto& x : A) { cin >> x; --x; }
	vector<int> P(N); for(int i = 0; i < N; i++) P[A[i]] = i;

	vector<vector<int>> adj(N), ADJ(N);
	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		if (A[u] < A[v]) swap(u, v);
		adj[u].push_back(v);
		adj[v].push_back(u);
		ADJ[u].push_back(v);
	}

	vector<vector<int>> up(N, vector<int>(LG));
	vector<int> dep(N);
	function<void(int, int)> dfs = [&](int u, int p) {
		up[u][0] = (p == -1 ? u : p);
		dep[u] = (p == -1 ? 0 : dep[p] + 1);

		for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

		for(auto v : adj[u]) if (v != p) dfs(v, u);
	};

	auto jmp = [&](int u, int d) {
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
		return u;
	};

	auto lca = [&](int u, int v) {
		if (dep[u] < dep[v]) swap(u, v);
		u = jmp(u, dep[u] - dep[v]);
		if (u == v) return u;
		for(int i = LG - 1; i >= 0; i--) if (up[u][i] != up[v][i]) {
			u = up[u][i], v = up[v][i];
		}
		return up[u][0];
	};

	auto dist = [&](int u, int v) {
		return dep[u] + dep[v] - 2*dep[lca(u, v)];
	};

	vector<ll> dp(N);

	dfs(0, -1);

	DSU d; d.init(N, A);

	for(int u = 0; u < N; u++) {
		for(auto v : ADJ[P[u]]) {
			int x = d.getmx(v); 
			// cout << u << " - " << P[u] << nl;
			// cout << v << " <> " << x << nl;
			dp[u] = max(dp[u], dp[x] + dist(P[u], P[x]));
		}
		for(auto v : ADJ[P[u]]) d.unite(P[u], v);
	}

	cout << dp[N - 1] << nl;


	return 0;
}

/*

4 
3 4 1 2  
1 2
2 3
3 4

7 
3 2 7 1 5 4 6  
1 2
1 3
2 4
2 5
3 6
3 7

*/

• 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