Submission #1215914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215914		trimkus	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	141 ms	38432 KiB

Main

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


const int MAXN = 2e5;
const int LOG = 20;
int lift[MAXN][LOG];
int depth[MAXN];

struct DSU {
	vector<int> e;
	DSU(int n) {
		e = vector<int>(n, -1);
	}
	int get(int x) {
		return e[x] < 0 ? x : e[x] = get(e[x]);
	}
	void unite(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) return;
		if (x < y) swap(x, y);
		e[x] += e[y];
		e[y] = x;
	}
};


int lca(int v, int u) {
	if (depth[v] < depth[u]) swap(v, u);
	int diff = depth[v] - depth[u];
	for (int k = 0; k < LOG; ++k) {
		if (diff >> k & 1) {
			v = lift[v][k];
		}
	}
	if (v == u) return v;
	for (int k = LOG - 1; k >= 0; --k) {
		if (lift[v][k] == -1) continue;
		if (lift[v][k] != lift[u][k]) {
			v = lift[v][k];
			u = lift[u][k];
		}
	}
	assert(lift[v][0] == lift[u][0]);
	return lift[v][0];
}

int get_dist(int v, int u) {
	int ancestor = lca(v, u);
	return depth[v] + depth[u] - 2 * depth[ancestor];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n), ra(n + 1);
	int root = -1;
	vector<vector<int>> adj(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		ra[a[i]] = i;
		if (a[i] == n) root = i;
	}
	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	DSU dsu(n + 1);
	auto dfs = [&](auto& dfs, int v, int p) -> void {
		for (auto& u : adj[v]) {
			if (u == p) continue;
			depth[u] = depth[v] + 1;
			dfs(dfs, u, v);
			lift[u][0] = v;
		}
	};
	for (auto& v : lift) for (auto& u : v) u = -1;
	dfs(dfs, 0, -1);
	for (int l = 1; l < LOG; ++l) {
		for (int i = 0; i < n; ++i) {
			if (lift[i][l - 1] == -1) continue;
			lift[i][l] = lift[lift[i][l - 1]][l - 1];
		}
	}
	//~ cerr << "a\n";
	vector<ll> dp(n + 1);
	for (int x = 1; x <= n; ++x) {
		int i = ra[x];
		ll res = 0;
		for (auto& u : adj[i]) {
			if (a[i] > a[u]) {
				int mx = dsu.get(a[u]);
				res = max(res, get_dist(i, ra[mx]) + dp[mx]);
				//~ cerr << i << " -> " << u get_dist(i, u) << " " << dp[dsu.get(u)] << " " << res << "\n";;
				dsu.unite(a[i], a[u]);
			}
		}
		assert(dsu.get(x) == x);
		dp[x] = res;
		//~ for (int i = 1; i <= n; ++i) {
			//~ cout << dp[dsu.get(i)] << " ";
		//~ }
		//~ cout << "\n";
	}
	cout << dp[n] << "\n";
}

• 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