oj.uz

Submission #1111865

# Submission time Handle Problem Language Result Execution time Memory
1111865 2024-11-13T08:15:18 Z starchan Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 151 ms 63560 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;
const int INF = 1e17;
const int LOGM = 18;

vector<int> adj[MX];

int par[LOGM][MX]; int dp[MX]; int dep[MX]; int tin[MX]; int tout[MX];

int T;

void dfs(int u, int p)
{
	tin[u] = ++T;
	par[0][u] = p;
	dep[u] = dep[p]+1;
	for(int v: adj[u])
	{
		if(v == p)
			continue;
		dfs(v, u);
	}
	tout[u] = T;
	return;
}

int dist(int u, int v)
{
	if(tin[u] > tin[v])
		swap(u, v);
	if(tout[u] >= tout[v])
		return dep[v]-dep[u];
	int s = u;
	for(int i = LOGM-1; i >= 0; i--)
	{
		if(tout[par[i][s]] < tout[v])
			s = par[i][s];
	}
	s = par[0][s];
	return dep[u]+dep[v]-2*dep[s];
}

vector<int> bst(MX);
vector<int> pa(MX, -1);

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	return pa[u] = leader(pa[u]);
}

void merge(int u, int v)
{
	u = leader(u);
	v = leader(v);
	if(u == v)
		return;
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v]+=pa[u];
	bst[v] = max(bst[v], bst[u]);
	pa[u] = v;
	return;
}

signed main()
{
	fast();
	int n; cin >> n;
	vector<int> p(n+1);
	for(int i = 1; i <= n; i++)
		cin >> p[i];
	for(int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		u = p[u]; v = p[v];
		adj[u].pb(v); adj[v].pb(u);
	}
	par[0][0] = 0; dep[0] = 0; tout[0] = n+5;
	dfs(1, 0);
	for(int i = 1; i < LOGM; i++)
	{
		for(int u = 1; u <= n; u++)
			par[i][u] = par[i-1][par[i-1][u]];
	}
	for(int i = 1; i <= n; i++)
		bst[i] = i;
	for(int i = 1; i <= n; i++)
	{
		for(int j: adj[i])
		{
			if(j < i)
			{
				int w = bst[leader(j)];
				dp[i] = max(dp[i], dp[w]+dist(i, w));
				merge(i, j);
			}
		}
	}
	cout << dp[n] << "\n";
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 42320 KB Output is correct
2 Correct 9 ms 42320 KB Output is correct
3 Correct 8 ms 42320 KB Output is correct
4 Correct 8 ms 42492 KB Output is correct
5 Correct 8 ms 42320 KB Output is correct
6 Correct 8 ms 42320 KB Output is correct
7 Correct 8 ms 42320 KB Output is correct
8 Correct 7 ms 42320 KB Output is correct
9 Correct 8 ms 40272 KB Output is correct
10 Correct 8 ms 38224 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 42320 KB Output is correct
2 Correct 9 ms 42320 KB Output is correct
3 Correct 8 ms 42320 KB Output is correct
4 Correct 8 ms 42492 KB Output is correct
5 Correct 8 ms 42320 KB Output is correct
6 Correct 8 ms 42320 KB Output is correct
7 Correct 8 ms 42320 KB Output is correct
8 Correct 7 ms 42320 KB Output is correct
9 Correct 8 ms 40272 KB Output is correct
10 Correct 8 ms 38224 KB Output is correct
11 Correct 8 ms 36432 KB Output is correct
12 Correct 8 ms 36368 KB Output is correct
13 Correct 8 ms 42580 KB Output is correct
14 Correct 8 ms 40448 KB Output is correct
15 Correct 8 ms 38480 KB Output is correct
16 Correct 8 ms 40528 KB Output is correct
17 Correct 9 ms 40528 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 42320 KB Output is correct
2 Correct 9 ms 42320 KB Output is correct
3 Correct 8 ms 42320 KB Output is correct
4 Correct 8 ms 42492 KB Output is correct
5 Correct 8 ms 42320 KB Output is correct
6 Correct 8 ms 42320 KB Output is correct
7 Correct 8 ms 42320 KB Output is correct
8 Correct 7 ms 42320 KB Output is correct
9 Correct 8 ms 40272 KB Output is correct
10 Correct 8 ms 38224 KB Output is correct
11 Correct 8 ms 36432 KB Output is correct
12 Correct 8 ms 36368 KB Output is correct
13 Correct 8 ms 42580 KB Output is correct
14 Correct 8 ms 40448 KB Output is correct
15 Correct 8 ms 38480 KB Output is correct
16 Correct 8 ms 40528 KB Output is correct
17 Correct 9 ms 40528 KB Output is correct
18 Correct 11 ms 36944 KB Output is correct
19 Correct 9 ms 35152 KB Output is correct
20 Correct 9 ms 35152 KB Output is correct
21 Correct 10 ms 40784 KB Output is correct
22 Correct 10 ms 42832 KB Output is correct
23 Correct 9 ms 42832 KB Output is correct
24 Correct 9 ms 42832 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 42320 KB Output is correct
2 Correct 9 ms 42320 KB Output is correct
3 Correct 8 ms 42320 KB Output is correct
4 Correct 8 ms 42492 KB Output is correct
5 Correct 8 ms 42320 KB Output is correct
6 Correct 8 ms 42320 KB Output is correct
7 Correct 8 ms 42320 KB Output is correct
8 Correct 7 ms 42320 KB Output is correct
9 Correct 8 ms 40272 KB Output is correct
10 Correct 8 ms 38224 KB Output is correct
11 Correct 8 ms 36432 KB Output is correct
12 Correct 8 ms 36368 KB Output is correct
13 Correct 8 ms 42580 KB Output is correct
14 Correct 8 ms 40448 KB Output is correct
15 Correct 8 ms 38480 KB Output is correct
16 Correct 8 ms 40528 KB Output is correct
17 Correct 9 ms 40528 KB Output is correct
18 Correct 11 ms 36944 KB Output is correct
19 Correct 9 ms 35152 KB Output is correct
20 Correct 9 ms 35152 KB Output is correct
21 Correct 10 ms 40784 KB Output is correct
22 Correct 10 ms 42832 KB Output is correct
23 Correct 9 ms 42832 KB Output is correct
24 Correct 9 ms 42832 KB Output is correct
25 Correct 7 ms 40272 KB Output is correct
26 Correct 9 ms 41040 KB Output is correct
27 Correct 9 ms 41040 KB Output is correct
28 Correct 9 ms 42832 KB Output is correct
29 Correct 9 ms 42832 KB Output is correct
30 Correct 9 ms 43084 KB Output is correct
31 Correct 9 ms 40784 KB Output is correct
32 Correct 9 ms 42784 KB Output is correct
33 Correct 9 ms 42832 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 42320 KB Output is correct
2 Correct 9 ms 42320 KB Output is correct
3 Correct 8 ms 42320 KB Output is correct
4 Correct 8 ms 42492 KB Output is correct
5 Correct 8 ms 42320 KB Output is correct
6 Correct 8 ms 42320 KB Output is correct
7 Correct 8 ms 42320 KB Output is correct
8 Correct 7 ms 42320 KB Output is correct
9 Correct 8 ms 40272 KB Output is correct
10 Correct 8 ms 38224 KB Output is correct
11 Correct 8 ms 36432 KB Output is correct
12 Correct 8 ms 36368 KB Output is correct
13 Correct 8 ms 42580 KB Output is correct
14 Correct 8 ms 40448 KB Output is correct
15 Correct 8 ms 38480 KB Output is correct
16 Correct 8 ms 40528 KB Output is correct
17 Correct 9 ms 40528 KB Output is correct
18 Correct 11 ms 36944 KB Output is correct
19 Correct 9 ms 35152 KB Output is correct
20 Correct 9 ms 35152 KB Output is correct
21 Correct 10 ms 40784 KB Output is correct
22 Correct 10 ms 42832 KB Output is correct
23 Correct 9 ms 42832 KB Output is correct
24 Correct 9 ms 42832 KB Output is correct
25 Correct 74 ms 58864 KB Output is correct
26 Correct 77 ms 63560 KB Output is correct
27 Correct 70 ms 63560 KB Output is correct
28 Correct 86 ms 63048 KB Output is correct
29 Correct 92 ms 58952 KB Output is correct
30 Correct 104 ms 62024 KB Output is correct
31 Correct 98 ms 61000 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 42320 KB Output is correct
2 Correct 8 ms 42320 KB Output is correct
3 Correct 104 ms 55744 KB Output is correct
4 Correct 115 ms 55660 KB Output is correct
5 Correct 106 ms 55624 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 42320 KB Output is correct
2 Correct 9 ms 42320 KB Output is correct
3 Correct 8 ms 42320 KB Output is correct
4 Correct 8 ms 42492 KB Output is correct
5 Correct 8 ms 42320 KB Output is correct
6 Correct 8 ms 42320 KB Output is correct
7 Correct 8 ms 42320 KB Output is correct
8 Correct 7 ms 42320 KB Output is correct
9 Correct 8 ms 40272 KB Output is correct
10 Correct 8 ms 38224 KB Output is correct
11 Correct 8 ms 36432 KB Output is correct
12 Correct 8 ms 36368 KB Output is correct
13 Correct 8 ms 42580 KB Output is correct
14 Correct 8 ms 40448 KB Output is correct
15 Correct 8 ms 38480 KB Output is correct
16 Correct 8 ms 40528 KB Output is correct
17 Correct 9 ms 40528 KB Output is correct
18 Correct 11 ms 36944 KB Output is correct
19 Correct 9 ms 35152 KB Output is correct
20 Correct 9 ms 35152 KB Output is correct
21 Correct 10 ms 40784 KB Output is correct
22 Correct 10 ms 42832 KB Output is correct
23 Correct 9 ms 42832 KB Output is correct
24 Correct 9 ms 42832 KB Output is correct
25 Correct 7 ms 40272 KB Output is correct
26 Correct 9 ms 41040 KB Output is correct
27 Correct 9 ms 41040 KB Output is correct
28 Correct 9 ms 42832 KB Output is correct
29 Correct 9 ms 42832 KB Output is correct
30 Correct 9 ms 43084 KB Output is correct
31 Correct 9 ms 40784 KB Output is correct
32 Correct 9 ms 42784 KB Output is correct
33 Correct 9 ms 42832 KB Output is correct
34 Correct 74 ms 58864 KB Output is correct
35 Correct 77 ms 63560 KB Output is correct
36 Correct 70 ms 63560 KB Output is correct
37 Correct 86 ms 63048 KB Output is correct
38 Correct 92 ms 58952 KB Output is correct
39 Correct 104 ms 62024 KB Output is correct
40 Correct 98 ms 61000 KB Output is correct
41 Correct 10 ms 42320 KB Output is correct
42 Correct 8 ms 42320 KB Output is correct
43 Correct 104 ms 55744 KB Output is correct
44 Correct 115 ms 55660 KB Output is correct
45 Correct 106 ms 55624 KB Output is correct
46 Correct 92 ms 61256 KB Output is correct
47 Correct 99 ms 61188 KB Output is correct
48 Correct 86 ms 61376 KB Output is correct
49 Correct 88 ms 61256 KB Output is correct
50 Correct 125 ms 55320 KB Output is correct
51 Correct 139 ms 55112 KB Output is correct
52 Correct 125 ms 55368 KB Output is correct
53 Correct 151 ms 55112 KB Output is correct