답안 #988223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
988223	2024-05-24T10:12:46 Z	dubabuba	Cat Exercise (JOI23_ho_t4)	C++14	21 / 100	2000 ms	106156 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 = 1e6 + 3;
const int inf = 1e9 + 9;

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]);
		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

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	53848 KB	Output is correct
2	Correct	12 ms	54016 KB	Output is correct
3	Correct	12 ms	53848 KB	Output is correct
4	Correct	12 ms	53852 KB	Output is correct
5	Correct	12 ms	53852 KB	Output is correct
6	Correct	11 ms	56120 KB	Output is correct
7	Correct	13 ms	53852 KB	Output is correct
8	Correct	12 ms	53848 KB	Output is correct
9	Correct	12 ms	53848 KB	Output is correct
10	Correct	12 ms	53852 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	53848 KB	Output is correct
2	Correct	12 ms	54016 KB	Output is correct
3	Correct	12 ms	53848 KB	Output is correct
4	Correct	12 ms	53852 KB	Output is correct
5	Correct	12 ms	53852 KB	Output is correct
6	Correct	11 ms	56120 KB	Output is correct
7	Correct	13 ms	53852 KB	Output is correct
8	Correct	12 ms	53848 KB	Output is correct
9	Correct	12 ms	53848 KB	Output is correct
10	Correct	12 ms	53852 KB	Output is correct
11	Correct	14 ms	56156 KB	Output is correct
12	Correct	13 ms	54108 KB	Output is correct
13	Correct	15 ms	54108 KB	Output is correct
14	Correct	14 ms	56156 KB	Output is correct
15	Correct	14 ms	54104 KB	Output is correct
16	Correct	14 ms	54360 KB	Output is correct
17	Correct	14 ms	56156 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	53848 KB	Output is correct
2	Correct	12 ms	54016 KB	Output is correct
3	Correct	12 ms	53848 KB	Output is correct
4	Correct	12 ms	53852 KB	Output is correct
5	Correct	12 ms	53852 KB	Output is correct
6	Correct	11 ms	56120 KB	Output is correct
7	Correct	13 ms	53852 KB	Output is correct
8	Correct	12 ms	53848 KB	Output is correct
9	Correct	12 ms	53848 KB	Output is correct
10	Correct	12 ms	53852 KB	Output is correct
11	Correct	14 ms	56156 KB	Output is correct
12	Correct	13 ms	54108 KB	Output is correct
13	Correct	15 ms	54108 KB	Output is correct
14	Correct	14 ms	56156 KB	Output is correct
15	Correct	14 ms	54104 KB	Output is correct
16	Correct	14 ms	54360 KB	Output is correct
17	Correct	14 ms	56156 KB	Output is correct
18	Correct	914 ms	55476 KB	Output is correct
19	Correct	854 ms	57256 KB	Output is correct
20	Correct	860 ms	57424 KB	Output is correct
21	Correct	858 ms	57208 KB	Output is correct
22	Correct	807 ms	57384 KB	Output is correct
23	Correct	802 ms	57168 KB	Output is correct
24	Correct	810 ms	57104 KB	Output is correct

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	53848 KB	Output is correct
2	Correct	12 ms	54016 KB	Output is correct
3	Correct	12 ms	53848 KB	Output is correct
4	Correct	12 ms	53852 KB	Output is correct
5	Correct	12 ms	53852 KB	Output is correct
6	Correct	11 ms	56120 KB	Output is correct
7	Correct	13 ms	53852 KB	Output is correct
8	Correct	12 ms	53848 KB	Output is correct
9	Correct	12 ms	53848 KB	Output is correct
10	Correct	12 ms	53852 KB	Output is correct
11	Correct	14 ms	56156 KB	Output is correct
12	Correct	13 ms	54108 KB	Output is correct
13	Correct	15 ms	54108 KB	Output is correct
14	Correct	14 ms	56156 KB	Output is correct
15	Correct	14 ms	54104 KB	Output is correct
16	Correct	14 ms	54360 KB	Output is correct
17	Correct	14 ms	56156 KB	Output is correct
18	Correct	914 ms	55476 KB	Output is correct
19	Correct	854 ms	57256 KB	Output is correct
20	Correct	860 ms	57424 KB	Output is correct
21	Correct	858 ms	57208 KB	Output is correct
22	Correct	807 ms	57384 KB	Output is correct
23	Correct	802 ms	57168 KB	Output is correct
24	Correct	810 ms	57104 KB	Output is correct
25	Correct	11 ms	53852 KB	Output is correct
26	Correct	889 ms	55392 KB	Output is correct
27	Correct	888 ms	55140 KB	Output is correct
28	Correct	884 ms	55168 KB	Output is correct
29	Correct	1103 ms	47188 KB	Output is correct
30	Incorrect	700 ms	47176 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	53848 KB	Output is correct
2	Correct	12 ms	54016 KB	Output is correct
3	Correct	12 ms	53848 KB	Output is correct
4	Correct	12 ms	53852 KB	Output is correct
5	Correct	12 ms	53852 KB	Output is correct
6	Correct	11 ms	56120 KB	Output is correct
7	Correct	13 ms	53852 KB	Output is correct
8	Correct	12 ms	53848 KB	Output is correct
9	Correct	12 ms	53848 KB	Output is correct
10	Correct	12 ms	53852 KB	Output is correct
11	Correct	14 ms	56156 KB	Output is correct
12	Correct	13 ms	54108 KB	Output is correct
13	Correct	15 ms	54108 KB	Output is correct
14	Correct	14 ms	56156 KB	Output is correct
15	Correct	14 ms	54104 KB	Output is correct
16	Correct	14 ms	54360 KB	Output is correct
17	Correct	14 ms	56156 KB	Output is correct
18	Correct	914 ms	55476 KB	Output is correct
19	Correct	854 ms	57256 KB	Output is correct
20	Correct	860 ms	57424 KB	Output is correct
21	Correct	858 ms	57208 KB	Output is correct
22	Correct	807 ms	57384 KB	Output is correct
23	Correct	802 ms	57168 KB	Output is correct
24	Correct	810 ms	57104 KB	Output is correct
25	Execution timed out	2072 ms	106156 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	45660 KB	Output is correct
2	Incorrect	12 ms	47960 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	53848 KB	Output is correct
2	Correct	12 ms	54016 KB	Output is correct
3	Correct	12 ms	53848 KB	Output is correct
4	Correct	12 ms	53852 KB	Output is correct
5	Correct	12 ms	53852 KB	Output is correct
6	Correct	11 ms	56120 KB	Output is correct
7	Correct	13 ms	53852 KB	Output is correct
8	Correct	12 ms	53848 KB	Output is correct
9	Correct	12 ms	53848 KB	Output is correct
10	Correct	12 ms	53852 KB	Output is correct
11	Correct	14 ms	56156 KB	Output is correct
12	Correct	13 ms	54108 KB	Output is correct
13	Correct	15 ms	54108 KB	Output is correct
14	Correct	14 ms	56156 KB	Output is correct
15	Correct	14 ms	54104 KB	Output is correct
16	Correct	14 ms	54360 KB	Output is correct
17	Correct	14 ms	56156 KB	Output is correct
18	Correct	914 ms	55476 KB	Output is correct
19	Correct	854 ms	57256 KB	Output is correct
20	Correct	860 ms	57424 KB	Output is correct
21	Correct	858 ms	57208 KB	Output is correct
22	Correct	807 ms	57384 KB	Output is correct
23	Correct	802 ms	57168 KB	Output is correct
24	Correct	810 ms	57104 KB	Output is correct
25	Correct	11 ms	53852 KB	Output is correct
26	Correct	889 ms	55392 KB	Output is correct
27	Correct	888 ms	55140 KB	Output is correct
28	Correct	884 ms	55168 KB	Output is correct
29	Correct	1103 ms	47188 KB	Output is correct
30	Incorrect	700 ms	47176 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

답안 #988223

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

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

Subtask #5
0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0