Submission #988226

# Submission time Handle Problem Language Result Execution time Memory
988226 2024-05-24T10:18:22 Z dubabuba Cat Exercise (JOI23_ho_t4) C++14
31 / 100
2000 ms 60496 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39260 KB Output is correct
3 Correct 7 ms 39408 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 6 ms 39260 KB Output is correct
6 Correct 6 ms 39456 KB Output is correct
7 Correct 7 ms 39304 KB Output is correct
8 Correct 7 ms 39260 KB Output is correct
9 Correct 7 ms 39260 KB Output is correct
10 Correct 6 ms 39260 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39260 KB Output is correct
3 Correct 7 ms 39408 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 6 ms 39260 KB Output is correct
6 Correct 6 ms 39456 KB Output is correct
7 Correct 7 ms 39304 KB Output is correct
8 Correct 7 ms 39260 KB Output is correct
9 Correct 7 ms 39260 KB Output is correct
10 Correct 6 ms 39260 KB Output is correct
11 Correct 10 ms 39452 KB Output is correct
12 Correct 9 ms 39260 KB Output is correct
13 Correct 10 ms 39260 KB Output is correct
14 Correct 10 ms 39480 KB Output is correct
15 Correct 9 ms 39256 KB Output is correct
16 Correct 9 ms 39260 KB Output is correct
17 Correct 9 ms 39260 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39260 KB Output is correct
3 Correct 7 ms 39408 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 6 ms 39260 KB Output is correct
6 Correct 6 ms 39456 KB Output is correct
7 Correct 7 ms 39304 KB Output is correct
8 Correct 7 ms 39260 KB Output is correct
9 Correct 7 ms 39260 KB Output is correct
10 Correct 6 ms 39260 KB Output is correct
11 Correct 10 ms 39452 KB Output is correct
12 Correct 9 ms 39260 KB Output is correct
13 Correct 10 ms 39260 KB Output is correct
14 Correct 10 ms 39480 KB Output is correct
15 Correct 9 ms 39256 KB Output is correct
16 Correct 9 ms 39260 KB Output is correct
17 Correct 9 ms 39260 KB Output is correct
18 Correct 936 ms 39772 KB Output is correct
19 Correct 906 ms 39956 KB Output is correct
20 Correct 900 ms 39956 KB Output is correct
21 Correct 886 ms 39900 KB Output is correct
22 Correct 866 ms 40020 KB Output is correct
23 Correct 866 ms 40080 KB Output is correct
24 Correct 861 ms 39800 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39260 KB Output is correct
3 Correct 7 ms 39408 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 6 ms 39260 KB Output is correct
6 Correct 6 ms 39456 KB Output is correct
7 Correct 7 ms 39304 KB Output is correct
8 Correct 7 ms 39260 KB Output is correct
9 Correct 7 ms 39260 KB Output is correct
10 Correct 6 ms 39260 KB Output is correct
11 Correct 10 ms 39452 KB Output is correct
12 Correct 9 ms 39260 KB Output is correct
13 Correct 10 ms 39260 KB Output is correct
14 Correct 10 ms 39480 KB Output is correct
15 Correct 9 ms 39256 KB Output is correct
16 Correct 9 ms 39260 KB Output is correct
17 Correct 9 ms 39260 KB Output is correct
18 Correct 936 ms 39772 KB Output is correct
19 Correct 906 ms 39956 KB Output is correct
20 Correct 900 ms 39956 KB Output is correct
21 Correct 886 ms 39900 KB Output is correct
22 Correct 866 ms 40020 KB Output is correct
23 Correct 866 ms 40080 KB Output is correct
24 Correct 861 ms 39800 KB Output is correct
25 Correct 6 ms 39260 KB Output is correct
26 Correct 923 ms 39872 KB Output is correct
27 Correct 912 ms 39868 KB Output is correct
28 Correct 914 ms 40016 KB Output is correct
29 Correct 909 ms 39900 KB Output is correct
30 Correct 720 ms 39516 KB Output is correct
31 Correct 717 ms 39732 KB Output is correct
32 Correct 736 ms 39740 KB Output is correct
33 Correct 735 ms 39740 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39260 KB Output is correct
3 Correct 7 ms 39408 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 6 ms 39260 KB Output is correct
6 Correct 6 ms 39456 KB Output is correct
7 Correct 7 ms 39304 KB Output is correct
8 Correct 7 ms 39260 KB Output is correct
9 Correct 7 ms 39260 KB Output is correct
10 Correct 6 ms 39260 KB Output is correct
11 Correct 10 ms 39452 KB Output is correct
12 Correct 9 ms 39260 KB Output is correct
13 Correct 10 ms 39260 KB Output is correct
14 Correct 10 ms 39480 KB Output is correct
15 Correct 9 ms 39256 KB Output is correct
16 Correct 9 ms 39260 KB Output is correct
17 Correct 9 ms 39260 KB Output is correct
18 Correct 936 ms 39772 KB Output is correct
19 Correct 906 ms 39956 KB Output is correct
20 Correct 900 ms 39956 KB Output is correct
21 Correct 886 ms 39900 KB Output is correct
22 Correct 866 ms 40020 KB Output is correct
23 Correct 866 ms 40080 KB Output is correct
24 Correct 861 ms 39800 KB Output is correct
25 Execution timed out 2045 ms 60496 KB Time limit exceeded
26 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 8 ms 39260 KB Output is correct
2 Correct 8 ms 39468 KB Output is correct
3 Execution timed out 2004 ms 51524 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 39256 KB Output is correct
2 Correct 6 ms 39260 KB Output is correct
3 Correct 7 ms 39408 KB Output is correct
4 Correct 7 ms 39260 KB Output is correct
5 Correct 6 ms 39260 KB Output is correct
6 Correct 6 ms 39456 KB Output is correct
7 Correct 7 ms 39304 KB Output is correct
8 Correct 7 ms 39260 KB Output is correct
9 Correct 7 ms 39260 KB Output is correct
10 Correct 6 ms 39260 KB Output is correct
11 Correct 10 ms 39452 KB Output is correct
12 Correct 9 ms 39260 KB Output is correct
13 Correct 10 ms 39260 KB Output is correct
14 Correct 10 ms 39480 KB Output is correct
15 Correct 9 ms 39256 KB Output is correct
16 Correct 9 ms 39260 KB Output is correct
17 Correct 9 ms 39260 KB Output is correct
18 Correct 936 ms 39772 KB Output is correct
19 Correct 906 ms 39956 KB Output is correct
20 Correct 900 ms 39956 KB Output is correct
21 Correct 886 ms 39900 KB Output is correct
22 Correct 866 ms 40020 KB Output is correct
23 Correct 866 ms 40080 KB Output is correct
24 Correct 861 ms 39800 KB Output is correct
25 Correct 6 ms 39260 KB Output is correct
26 Correct 923 ms 39872 KB Output is correct
27 Correct 912 ms 39868 KB Output is correct
28 Correct 914 ms 40016 KB Output is correct
29 Correct 909 ms 39900 KB Output is correct
30 Correct 720 ms 39516 KB Output is correct
31 Correct 717 ms 39732 KB Output is correct
32 Correct 736 ms 39740 KB Output is correct
33 Correct 735 ms 39740 KB Output is correct
34 Execution timed out 2045 ms 60496 KB Time limit exceeded
35 Halted 0 ms 0 KB -