답안 #938820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938820	2024-03-05T15:32:44 Z	THXuan	Cat Exercise (JOI23_ho_t4)	C++14	54 / 100	322 ms	89848 KB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e18
using namespace std;
typedef long long ll;

vector<int>adj[2000005];
int d[2000005],par[2000005], p[2000005][25], dp[2000005];

void dfs(int s, int e) {
	for (int i = 1; i <=20; i++) {
		p[s][i] = p[p[s][i - 1]][i - 1];
	}
	for (auto u : adj[s]) {
		if (u == e) continue;
		d[u] = d[s] + 1;
		p[u][0] = s;
		dfs(u, s);
	}
}

int lca(int a, int b) {
	if (d[a] > d[b]) swap(a, b);
	int dist = d[b] - d[a];
	for (int i = 0; i <= 20; i++) {
		if (dist & (1 << i))b = p[b][i];
	}
	if (a == b) return a;
	for (int i = 20; i >= 0; i--) {
		if (p[a][i] != p[b][i]) {
			a = p[a][i];
			b = p[b][i];
		}
	}
	return p[a][0];
}

int find(int x) {
	while (x != par[x])x = par[x];
	return x;
}

int get_dist(int a, int b) {
	int lcaa = lca(a, b);
	return (d[a] - d[lcaa]) + (d[b] - d[lcaa]);
}

void solve()
{
	int n; cin >> n;
	vector<int>v(n + 1);
	for (int i = 1; i <= n; i++) cin >> v[i];
	for (int i = 1; i <= n - 1; i++) {
		int a, b; cin >> a >> b;
		a = v[a]; b = v[b];
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) par[i] = i;
	for (int i = 1; i <= n; i++) {
		for (auto u : adj[i]) {
			u = find(u);
			if (u < i) {
				par[u] = i;
				dp[i] = max(dp[i], dp[u] + get_dist(i, u));
			}
		}
	}
	cout << dp[n] << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	50776 KB	Output is correct
2	Correct	11 ms	50780 KB	Output is correct
3	Correct	12 ms	50780 KB	Output is correct
4	Correct	11 ms	50780 KB	Output is correct
5	Correct	11 ms	50780 KB	Output is correct
6	Correct	12 ms	50980 KB	Output is correct
7	Correct	12 ms	50780 KB	Output is correct
8	Correct	11 ms	50776 KB	Output is correct
9	Correct	13 ms	50780 KB	Output is correct
10	Correct	12 ms	50924 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	50776 KB	Output is correct
2	Correct	11 ms	50780 KB	Output is correct
3	Correct	12 ms	50780 KB	Output is correct
4	Correct	11 ms	50780 KB	Output is correct
5	Correct	11 ms	50780 KB	Output is correct
6	Correct	12 ms	50980 KB	Output is correct
7	Correct	12 ms	50780 KB	Output is correct
8	Correct	11 ms	50776 KB	Output is correct
9	Correct	13 ms	50780 KB	Output is correct
10	Correct	12 ms	50924 KB	Output is correct
11	Correct	12 ms	51036 KB	Output is correct
12	Correct	11 ms	51048 KB	Output is correct
13	Correct	11 ms	51036 KB	Output is correct
14	Correct	11 ms	50780 KB	Output is correct
15	Correct	11 ms	51036 KB	Output is correct
16	Correct	12 ms	50780 KB	Output is correct
17	Correct	11 ms	51036 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	50776 KB	Output is correct
2	Correct	11 ms	50780 KB	Output is correct
3	Correct	12 ms	50780 KB	Output is correct
4	Correct	11 ms	50780 KB	Output is correct
5	Correct	11 ms	50780 KB	Output is correct
6	Correct	12 ms	50980 KB	Output is correct
7	Correct	12 ms	50780 KB	Output is correct
8	Correct	11 ms	50776 KB	Output is correct
9	Correct	13 ms	50780 KB	Output is correct
10	Correct	12 ms	50924 KB	Output is correct
11	Correct	12 ms	51036 KB	Output is correct
12	Correct	11 ms	51048 KB	Output is correct
13	Correct	11 ms	51036 KB	Output is correct
14	Correct	11 ms	50780 KB	Output is correct
15	Correct	11 ms	51036 KB	Output is correct
16	Correct	12 ms	50780 KB	Output is correct
17	Correct	11 ms	51036 KB	Output is correct
18	Correct	14 ms	51800 KB	Output is correct
19	Correct	14 ms	51904 KB	Output is correct
20	Correct	14 ms	52060 KB	Output is correct
21	Correct	14 ms	51800 KB	Output is correct
22	Correct	15 ms	51804 KB	Output is correct
23	Correct	13 ms	51800 KB	Output is correct
24	Correct	14 ms	51804 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	50776 KB	Output is correct
2	Correct	11 ms	50780 KB	Output is correct
3	Correct	12 ms	50780 KB	Output is correct
4	Correct	11 ms	50780 KB	Output is correct
5	Correct	11 ms	50780 KB	Output is correct
6	Correct	12 ms	50980 KB	Output is correct
7	Correct	12 ms	50780 KB	Output is correct
8	Correct	11 ms	50776 KB	Output is correct
9	Correct	13 ms	50780 KB	Output is correct
10	Correct	12 ms	50924 KB	Output is correct
11	Correct	12 ms	51036 KB	Output is correct
12	Correct	11 ms	51048 KB	Output is correct
13	Correct	11 ms	51036 KB	Output is correct
14	Correct	11 ms	50780 KB	Output is correct
15	Correct	11 ms	51036 KB	Output is correct
16	Correct	12 ms	50780 KB	Output is correct
17	Correct	11 ms	51036 KB	Output is correct
18	Correct	14 ms	51800 KB	Output is correct
19	Correct	14 ms	51904 KB	Output is correct
20	Correct	14 ms	52060 KB	Output is correct
21	Correct	14 ms	51800 KB	Output is correct
22	Correct	15 ms	51804 KB	Output is correct
23	Correct	13 ms	51800 KB	Output is correct
24	Correct	14 ms	51804 KB	Output is correct
25	Correct	11 ms	50780 KB	Output is correct
26	Correct	13 ms	51724 KB	Output is correct
27	Correct	14 ms	51960 KB	Output is correct
28	Correct	14 ms	51804 KB	Output is correct
29	Correct	14 ms	51800 KB	Output is correct
30	Correct	14 ms	51548 KB	Output is correct
31	Correct	14 ms	51492 KB	Output is correct
32	Correct	14 ms	51548 KB	Output is correct
33	Correct	14 ms	51548 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	50776 KB	Output is correct
2	Correct	11 ms	50780 KB	Output is correct
3	Correct	12 ms	50780 KB	Output is correct
4	Correct	11 ms	50780 KB	Output is correct
5	Correct	11 ms	50780 KB	Output is correct
6	Correct	12 ms	50980 KB	Output is correct
7	Correct	12 ms	50780 KB	Output is correct
8	Correct	11 ms	50776 KB	Output is correct
9	Correct	13 ms	50780 KB	Output is correct
10	Correct	12 ms	50924 KB	Output is correct
11	Correct	12 ms	51036 KB	Output is correct
12	Correct	11 ms	51048 KB	Output is correct
13	Correct	11 ms	51036 KB	Output is correct
14	Correct	11 ms	50780 KB	Output is correct
15	Correct	11 ms	51036 KB	Output is correct
16	Correct	12 ms	50780 KB	Output is correct
17	Correct	11 ms	51036 KB	Output is correct
18	Correct	14 ms	51800 KB	Output is correct
19	Correct	14 ms	51904 KB	Output is correct
20	Correct	14 ms	52060 KB	Output is correct
21	Correct	14 ms	51800 KB	Output is correct
22	Correct	15 ms	51804 KB	Output is correct
23	Correct	13 ms	51800 KB	Output is correct
24	Correct	14 ms	51804 KB	Output is correct
25	Incorrect	114 ms	89848 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	50980 KB	Output is correct
2	Correct	11 ms	50780 KB	Output is correct
3	Correct	290 ms	82160 KB	Output is correct
4	Correct	322 ms	82256 KB	Output is correct
5	Correct	261 ms	81864 KB	Output is correct

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	50776 KB	Output is correct
2	Correct	11 ms	50780 KB	Output is correct
3	Correct	12 ms	50780 KB	Output is correct
4	Correct	11 ms	50780 KB	Output is correct
5	Correct	11 ms	50780 KB	Output is correct
6	Correct	12 ms	50980 KB	Output is correct
7	Correct	12 ms	50780 KB	Output is correct
8	Correct	11 ms	50776 KB	Output is correct
9	Correct	13 ms	50780 KB	Output is correct
10	Correct	12 ms	50924 KB	Output is correct
11	Correct	12 ms	51036 KB	Output is correct
12	Correct	11 ms	51048 KB	Output is correct
13	Correct	11 ms	51036 KB	Output is correct
14	Correct	11 ms	50780 KB	Output is correct
15	Correct	11 ms	51036 KB	Output is correct
16	Correct	12 ms	50780 KB	Output is correct
17	Correct	11 ms	51036 KB	Output is correct
18	Correct	14 ms	51800 KB	Output is correct
19	Correct	14 ms	51904 KB	Output is correct
20	Correct	14 ms	52060 KB	Output is correct
21	Correct	14 ms	51800 KB	Output is correct
22	Correct	15 ms	51804 KB	Output is correct
23	Correct	13 ms	51800 KB	Output is correct
24	Correct	14 ms	51804 KB	Output is correct
25	Correct	11 ms	50780 KB	Output is correct
26	Correct	13 ms	51724 KB	Output is correct
27	Correct	14 ms	51960 KB	Output is correct
28	Correct	14 ms	51804 KB	Output is correct
29	Correct	14 ms	51800 KB	Output is correct
30	Correct	14 ms	51548 KB	Output is correct
31	Correct	14 ms	51492 KB	Output is correct
32	Correct	14 ms	51548 KB	Output is correct
33	Correct	14 ms	51548 KB	Output is correct
34	Incorrect	114 ms	89848 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #938820

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 23.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
23.0 / 23.0

Subtask #7
0 / 26.0