Submission #988226

#	Time	Username	Problem	Language	Result	Execution time	Memory
988226		dubabuba	Cat Exercise (JOI23_ho_t4)	C++14	31 / 100	2045 ms	60496 KiB

Main

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxk = 22;
const int mxn = 2e5 + 10;
const int inf = 1e9 + 10;

int anc[mxk][mxn], lvl[mxn];
int mxu[mxk][mxn], h[mxn], n;
vector<int> adj[mxn];

void dfs(int u, int par = 0) {
	lvl[u] = lvl[par] + 1;
	for(int v : adj[u]) {
		if(v == par) continue;
		dfs(v, u);
		anc[0][v] = u;
		mxu[0][v] = max(u, v);
	}
}

int path(int u, int v) {
	int mx = 0, len = 0;
	int sussy = max(u, v);
	if(lvl[u] < lvl[v]) swap(u, v);

	int jump = lvl[u] - lvl[v];
	for(int k = 0; k < mxk; k++) {
		if(jump & (1 << k)) {
			jump ^= (1 << k);
			len += (1 << k);
			mx = max(mx, mxu[k][u]);
			u = anc[k][u];
		}
	}

	if(mx > sussy) return -inf;
	if(u == v) return len;

	for(int k = mxk - 1; k >= 0; k--)
	if(anc[k][u] != anc[k][v]) {
		mx = max(mx, mxu[k][u]);
		mx = max(mx, mxu[k][v]);
		len += (1 << (k + 1));
		u = anc[k][u];
		v = anc[k][v];
	}

	mx = max(mx, anc[0][u]);
	if(mx > sussy) return -inf;
	return len + 2;
}

int dp[mxn];

void solve() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> h[i];
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		u = h[u], v = h[v];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(n);
	for(int k = 1; k < mxk; k++)
	for(int i = 1; i <= n; i++) {
		int j = anc[k - 1][i];
		int m = mxu[k - 1][i];

		anc[k][i] = anc[k - 1][j];
		mxu[k][i] = max(m, mxu[k - 1][j]);
	}

	int ans = 0;
	for(int i = n - 1; i >= 1; i--) {
		// cout << i << endl;
		for(int j = i + 1; j <= n; j++) {
			dp[i] = max(dp[i], dp[j] + path(i, j));
			// cout << j << ' ' << dp[j] << ' ' << path(i, j) << endl;
		}
		// cout << i << ": " << dp[i] << endl;
		ans = max(ans, dp[i]);
	}

	cout << ans << endl;
}

signed main() {
	#ifdef LOCAL
		auto start = chrono::high_resolution_clock::now();
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	signed t = 1; // cin >> t;
	while(t--) solve();
	
	#ifdef LOCAL
		auto end = chrono::high_resolution_clock::now();
		cout << "\n"; for(int i = 0; i <= 20; ++i) cout << '-';
		cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
	#endif
	return 0;
}

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