oj.uz

Submission #1049584

# Submission time Handle Problem Language Result Execution time Memory
1049584 2024-08-09T00:14:40 Z ymm Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 95 ms 57428 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -