Submission #963134

#	Time	Username	Problem	Language	Result	Execution time	Memory
963134		dorulean	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	262 ms	52032 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
#define eb emplace_back

const int N = 2e5 + 5;
int a[N], ord[N], n, t[N], up[20][N], depth[N], dp[N];
vi g[N];
pii best[N];
bool active[N];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

 	cin >> n;
 	for (int i = 1; i <= n; ++i)
 		cin >> a[i], ord[i] = i, t[i] = i, best[i] = {a[i], i};
 	for (int u, v, i = 1; i < n; ++i) {
 		cin >> u >> v;
 		g[u].eb(v);
 		g[v].eb(u);
 	}
 	sort(ord + 1, ord + n + 1, [&](const int& i, const int& j) {return a[i] < a[j];});
 	
 	function<void(int,int)> dfs = [&](int u, int parent) {
 		up[0][u] = parent;
 		depth[u] = depth[parent] + 1;
 		for (auto v : g[u])
 			if (v != parent)
 				dfs(v, u);
 	};
	function<int(int,int)> lca = [&](int u, int v) {	
		if (depth[u] < depth[v])
			swap(u, v);
 		for (int p = 19; p >= 0; --p)
 			if (up[p][u] && depth[up[p][u]] >= depth[v])
 				u = up[p][u];
 		if (u == v) return u;
 		for (int p = 19; p >= 0; --p)
 			if (up[p][u] != up[p][v])
 				u = up[p][u], v = up[p][v];
 		return up[0][u];
 	};
 	function<int(int,int)> dist = [&](int u, int v) {
 		return depth[u] + depth[v] - 2 * depth[lca(u, v)];
 	};
 	function<int(int)> find = [&](int u) {
 		return (u == t[u] ? u : (t[u] = find(t[u])));
 	};
 	function<void(int,int)> join = [&](int u, int v) {
 		int ru = find(u), rv = find(v);
 		t[ru] = rv;
 		best[rv] = max(best[rv], best[ru]);
 	};
 	
 	dfs(1, 0);
 	for (int p = 1; p < 20; ++p)
 		for (int i = 1; i <= n; ++i)
 			up[p][i] = up[p - 1][up[p - 1][i]];
 	
 	for (int i = 1; i <= n; ++i) {
 		int u = ord[i];
 		active[u] = true;
 		for (auto v : g[u]) {
 			if (active[v]) {
 				int mx = best[find(v)].second;
 				dp[u] = max(dp[u], dp[mx] + dist(u, mx));
 				join(u, v);
 			}
 		}
 	}

 	cout << dp[ord[n]] << '\n';
} 

• 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