답안 #1049584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049584	2024-08-09T00:14:40 Z	ymm	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	95 ms	57428 KB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int lg = 20;
vector<int> A[N];
int val[N];
int anc[N][lg];
int height[N];

void dfs1(int v, int p, int h)
{
	anc[v][0] = p;
	Loop (i,0,lg-1)
		anc[v][i+1] = anc[anc[v][i]][i];
	height[v] = h;
	for (int u : A[v])
		if (u != p)
			dfs1(u, v, h+1);
}

int lca(int v, int u)
{
	if (height[v] < height[u])
		swap(v, u);
	int diff = height[v] - height[u];
	Loop (i,0,lg)
		if ((diff>>i)&1)
			v = anc[v][i];
	if (v == u)
		return v;
	LoopR (i,0,lg) {
		if (anc[v][i] != anc[u][i]) {
			v = anc[v][i];
			u = anc[u][i];
		}
	}
	return anc[v][0];
}

int dis(int v, int u)
{
	return height[v] + height[u] - 2 * height[lca(v, u)];
}

namespace dsu {
	int par[N];
	int p2[N];

	void init(int n) {
		fill(par, par+n, -1);
		fill(p2, p2+n, -1);
	}

	int rt(int v) { return p2[v] == -1? v: (p2[v] = rt(p2[v])); }

	void unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		par[u] = v;
		p2[u] = v;
	}
}

vector<int> A2[N];
int ans;

void dfs(int v, int h)
{
	ans = max(ans, h);
	for (int u : A2[v])
		dfs(u, h + dis(v, u));
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n;
	cin >> n;
	Loop (i,0,n)
		cin >> val[i];
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		v = val[v-1]-1;
		u = val[u-1]-1;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs1(0, 0, 0);
	dsu::init(n);
	Loop (v,0,n) {
		for (int u : A[v]) {
			if (v > u)
				dsu::unite(v, u);
		}
	}
	int rt = -1;
	Loop (i,0,n) {
		if (dsu::par[i] == -1)
			rt = i;
		else
			A2[dsu::par[i]].push_back(i);
	}
	dfs(rt, 0);
	cout << ans << '\n';
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16216 KB	Output is correct
2	Correct	2 ms	16220 KB	Output is correct
3	Correct	2 ms	16216 KB	Output is correct
4	Correct	2 ms	16324 KB	Output is correct
5	Correct	2 ms	16220 KB	Output is correct
6	Correct	2 ms	16220 KB	Output is correct
7	Correct	2 ms	16212 KB	Output is correct
8	Correct	2 ms	16220 KB	Output is correct
9	Correct	2 ms	16220 KB	Output is correct
10	Correct	2 ms	16220 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16216 KB	Output is correct
2	Correct	2 ms	16220 KB	Output is correct
3	Correct	2 ms	16216 KB	Output is correct
4	Correct	2 ms	16324 KB	Output is correct
5	Correct	2 ms	16220 KB	Output is correct
6	Correct	2 ms	16220 KB	Output is correct
7	Correct	2 ms	16212 KB	Output is correct
8	Correct	2 ms	16220 KB	Output is correct
9	Correct	2 ms	16220 KB	Output is correct
10	Correct	2 ms	16220 KB	Output is correct
11	Correct	2 ms	16216 KB	Output is correct
12	Correct	2 ms	16220 KB	Output is correct
13	Correct	2 ms	16220 KB	Output is correct
14	Correct	2 ms	16220 KB	Output is correct
15	Correct	2 ms	16220 KB	Output is correct
16	Correct	2 ms	16220 KB	Output is correct
17	Correct	2 ms	16284 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16216 KB	Output is correct
2	Correct	2 ms	16220 KB	Output is correct
3	Correct	2 ms	16216 KB	Output is correct
4	Correct	2 ms	16324 KB	Output is correct
5	Correct	2 ms	16220 KB	Output is correct
6	Correct	2 ms	16220 KB	Output is correct
7	Correct	2 ms	16212 KB	Output is correct
8	Correct	2 ms	16220 KB	Output is correct
9	Correct	2 ms	16220 KB	Output is correct
10	Correct	2 ms	16220 KB	Output is correct
11	Correct	2 ms	16216 KB	Output is correct
12	Correct	2 ms	16220 KB	Output is correct
13	Correct	2 ms	16220 KB	Output is correct
14	Correct	2 ms	16220 KB	Output is correct
15	Correct	2 ms	16220 KB	Output is correct
16	Correct	2 ms	16220 KB	Output is correct
17	Correct	2 ms	16284 KB	Output is correct
18	Correct	4 ms	16988 KB	Output is correct
19	Correct	3 ms	16732 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	5 ms	16732 KB	Output is correct
22	Correct	4 ms	16676 KB	Output is correct
23	Correct	4 ms	16732 KB	Output is correct
24	Correct	4 ms	16732 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16216 KB	Output is correct
2	Correct	2 ms	16220 KB	Output is correct
3	Correct	2 ms	16216 KB	Output is correct
4	Correct	2 ms	16324 KB	Output is correct
5	Correct	2 ms	16220 KB	Output is correct
6	Correct	2 ms	16220 KB	Output is correct
7	Correct	2 ms	16212 KB	Output is correct
8	Correct	2 ms	16220 KB	Output is correct
9	Correct	2 ms	16220 KB	Output is correct
10	Correct	2 ms	16220 KB	Output is correct
11	Correct	2 ms	16216 KB	Output is correct
12	Correct	2 ms	16220 KB	Output is correct
13	Correct	2 ms	16220 KB	Output is correct
14	Correct	2 ms	16220 KB	Output is correct
15	Correct	2 ms	16220 KB	Output is correct
16	Correct	2 ms	16220 KB	Output is correct
17	Correct	2 ms	16284 KB	Output is correct
18	Correct	4 ms	16988 KB	Output is correct
19	Correct	3 ms	16732 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	5 ms	16732 KB	Output is correct
22	Correct	4 ms	16676 KB	Output is correct
23	Correct	4 ms	16732 KB	Output is correct
24	Correct	4 ms	16732 KB	Output is correct
25	Correct	2 ms	16220 KB	Output is correct
26	Correct	4 ms	16728 KB	Output is correct
27	Correct	4 ms	16728 KB	Output is correct
28	Correct	3 ms	16732 KB	Output is correct
29	Correct	3 ms	16732 KB	Output is correct
30	Correct	4 ms	16476 KB	Output is correct
31	Correct	4 ms	16588 KB	Output is correct
32	Correct	4 ms	16476 KB	Output is correct
33	Correct	4 ms	16476 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16216 KB	Output is correct
2	Correct	2 ms	16220 KB	Output is correct
3	Correct	2 ms	16216 KB	Output is correct
4	Correct	2 ms	16324 KB	Output is correct
5	Correct	2 ms	16220 KB	Output is correct
6	Correct	2 ms	16220 KB	Output is correct
7	Correct	2 ms	16212 KB	Output is correct
8	Correct	2 ms	16220 KB	Output is correct
9	Correct	2 ms	16220 KB	Output is correct
10	Correct	2 ms	16220 KB	Output is correct
11	Correct	2 ms	16216 KB	Output is correct
12	Correct	2 ms	16220 KB	Output is correct
13	Correct	2 ms	16220 KB	Output is correct
14	Correct	2 ms	16220 KB	Output is correct
15	Correct	2 ms	16220 KB	Output is correct
16	Correct	2 ms	16220 KB	Output is correct
17	Correct	2 ms	16284 KB	Output is correct
18	Correct	4 ms	16988 KB	Output is correct
19	Correct	3 ms	16732 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	5 ms	16732 KB	Output is correct
22	Correct	4 ms	16676 KB	Output is correct
23	Correct	4 ms	16732 KB	Output is correct
24	Correct	4 ms	16732 KB	Output is correct
25	Incorrect	70 ms	57428 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16220 KB	Output is correct
2	Correct	2 ms	16220 KB	Output is correct
3	Correct	95 ms	43400 KB	Output is correct
4	Correct	87 ms	43412 KB	Output is correct
5	Correct	87 ms	43344 KB	Output is correct

Subtask #7
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16216 KB	Output is correct
2	Correct	2 ms	16220 KB	Output is correct
3	Correct	2 ms	16216 KB	Output is correct
4	Correct	2 ms	16324 KB	Output is correct
5	Correct	2 ms	16220 KB	Output is correct
6	Correct	2 ms	16220 KB	Output is correct
7	Correct	2 ms	16212 KB	Output is correct
8	Correct	2 ms	16220 KB	Output is correct
9	Correct	2 ms	16220 KB	Output is correct
10	Correct	2 ms	16220 KB	Output is correct
11	Correct	2 ms	16216 KB	Output is correct
12	Correct	2 ms	16220 KB	Output is correct
13	Correct	2 ms	16220 KB	Output is correct
14	Correct	2 ms	16220 KB	Output is correct
15	Correct	2 ms	16220 KB	Output is correct
16	Correct	2 ms	16220 KB	Output is correct
17	Correct	2 ms	16284 KB	Output is correct
18	Correct	4 ms	16988 KB	Output is correct
19	Correct	3 ms	16732 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	5 ms	16732 KB	Output is correct
22	Correct	4 ms	16676 KB	Output is correct
23	Correct	4 ms	16732 KB	Output is correct
24	Correct	4 ms	16732 KB	Output is correct
25	Correct	2 ms	16220 KB	Output is correct
26	Correct	4 ms	16728 KB	Output is correct
27	Correct	4 ms	16728 KB	Output is correct
28	Correct	3 ms	16732 KB	Output is correct
29	Correct	3 ms	16732 KB	Output is correct
30	Correct	4 ms	16476 KB	Output is correct
31	Correct	4 ms	16588 KB	Output is correct
32	Correct	4 ms	16476 KB	Output is correct
33	Correct	4 ms	16476 KB	Output is correct
34	Incorrect	70 ms	57428 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #1049584

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