Submission #963942

#	Time	Username	Problem	Language	Result	Execution time	Memory
963942		Gromp15	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	406 ms	46856 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
struct dsu {
	vector<int> p;
	dsu(int n) : p(n+1) {
		iota(all(p), 0);
	}
	int get(int v) {
		return v == p[v] ? v : p[v] = get(p[v]);
	}
	void merge(int a, int b) {
		a = get(a), b = get(b);
		if (a != b) p[b] = a;
	}
};
const int LOG = 18;
void test_case() {
	int n; cin >> n;
	vector<int> h(n+1);
	for (int i = 1; i <= n; i++) cin >> h[i];
	vector<vector<int>> adj(n+1);
	for (int i = 0; i < n-1; i++) {
		int x, y; cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	vector<vector<int>> up(n+1, vector<int>(LOG));
	vector<int> depth(n+1);
	auto dfs = [&](auto&& s, int v, int p) -> void {
		for (int u : adj[v]) if (u != p) {
			depth[u] = depth[v] + 1;
			up[u][0] = v;
			for (int i = 1; i < LOG; i++) {
				up[u][i] = up[up[u][i-1]][i-1];
			}
			s(s, u, v);
		}
	};
	dfs(dfs, 1, -1);
	auto lca = [&](int x, int y) {
		if (depth[x] < depth[y]) swap(x, y);
		int k = depth[x] - depth[y];
		for (int i = 0; i < LOG; i++) if (k >> i & 1) x = up[x][i];
		for (int i = LOG-1; i >= 0; i--) if (up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
		return x == y ? x : up[x][0];
	};
	auto dist = [&](int x, int y) {
		return depth[x] + depth[y] - 2 * depth[lca(x, y)];
	};
	vector<int> order(n);
	iota(all(order), 1);
	sort(all(order), [&](int x, int y) { return h[x] < h[y]; });
	vector<ll> dp(n+1, -1e18);
	dsu d(n);
	for (int v : order) {
		dp[v] = 0;
		for (int u : adj[v]) {
			u = d.get(u);
			if (h[v] > h[u]) { 
				ckmax(dp[v], dp[u] + dist(u, v));
				d.merge(v, u);
			}
		}
	}
	cout << *max_element(all(dp)) << '\n';


}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

• 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