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

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.0 / 7.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

Subtask #2
7.0 / 7.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
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

Subtask #3
7.0 / 7.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
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

Subtask #4
10.0 / 10.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
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

Subtask #5
0 / 20.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
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	-

Subtask #6
0 / 23.0

#	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	-

Subtask #7
0 / 26.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
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	-

Submission #988226

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0