oj.uz

Submission #963134

# Submission time Handle Problem Language Result Execution time Memory
963134 2024-04-14T14:56:23 Z dorulean Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 262 ms 52032 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using vi = vector<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
#define eb emplace_back

const int N = 2e5 + 5;
int a[N], ord[N], n, t[N], up[20][N], depth[N], dp[N];
vi g[N];
pii best[N];
bool active[N];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

 	cin >> n;
 	for (int i = 1; i <= n; ++i)
 		cin >> a[i], ord[i] = i, t[i] = i, best[i] = {a[i], i};
 	for (int u, v, i = 1; i < n; ++i) {
 		cin >> u >> v;
 		g[u].eb(v);
 		g[v].eb(u);
 	}
 	sort(ord + 1, ord + n + 1, [&](const int& i, const int& j) {return a[i] < a[j];});
 	
 	function<void(int,int)> dfs = [&](int u, int parent) {
 		up[0][u] = parent;
 		depth[u] = depth[parent] + 1;
 		for (auto v : g[u])
 			if (v != parent)
 				dfs(v, u);
 	};
	function<int(int,int)> lca = [&](int u, int v) {	
		if (depth[u] < depth[v])
			swap(u, v);
 		for (int p = 19; p >= 0; --p)
 			if (up[p][u] && depth[up[p][u]] >= depth[v])
 				u = up[p][u];
 		if (u == v) return u;
 		for (int p = 19; p >= 0; --p)
 			if (up[p][u] != up[p][v])
 				u = up[p][u], v = up[p][v];
 		return up[0][u];
 	};
 	function<int(int,int)> dist = [&](int u, int v) {
 		return depth[u] + depth[v] - 2 * depth[lca(u, v)];
 	};
 	function<int(int)> find = [&](int u) {
 		return (u == t[u] ? u : (t[u] = find(t[u])));
 	};
 	function<void(int,int)> join = [&](int u, int v) {
 		int ru = find(u), rv = find(v);
 		t[ru] = rv;
 		best[rv] = max(best[rv], best[ru]);
 	};
 	
 	dfs(1, 0);
 	for (int p = 1; p < 20; ++p)
 		for (int i = 1; i <= n; ++i)
 			up[p][i] = up[p - 1][up[p - 1][i]];
 	
 	for (int i = 1; i <= n; ++i) {
 		int u = ord[i];
 		active[u] = true;
 		for (auto v : g[u]) {
 			if (active[v]) {
 				int mx = best[find(v)].second;
 				dp[u] = max(dp[u], dp[mx] + dist(u, mx));
 				join(u, v);
 			}
 		}
 	}

 	cout << dp[ord[n]] << '\n';
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25308 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24920 KB Output is correct
4 Correct 4 ms 24924 KB Output is correct
5 Correct 3 ms 24924 KB Output is correct
6 Correct 3 ms 24924 KB Output is correct
7 Correct 4 ms 25064 KB Output is correct
8 Correct 4 ms 24924 KB Output is correct
9 Correct 4 ms 24924 KB Output is correct
10 Correct 4 ms 25060 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25308 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24920 KB Output is correct
4 Correct 4 ms 24924 KB Output is correct
5 Correct 3 ms 24924 KB Output is correct
6 Correct 3 ms 24924 KB Output is correct
7 Correct 4 ms 25064 KB Output is correct
8 Correct 4 ms 24924 KB Output is correct
9 Correct 4 ms 24924 KB Output is correct
10 Correct 4 ms 25060 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 4 ms 25116 KB Output is correct
14 Correct 4 ms 24920 KB Output is correct
15 Correct 4 ms 25176 KB Output is correct
16 Correct 5 ms 24928 KB Output is correct
17 Correct 4 ms 25052 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25308 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24920 KB Output is correct
4 Correct 4 ms 24924 KB Output is correct
5 Correct 3 ms 24924 KB Output is correct
6 Correct 3 ms 24924 KB Output is correct
7 Correct 4 ms 25064 KB Output is correct
8 Correct 4 ms 24924 KB Output is correct
9 Correct 4 ms 24924 KB Output is correct
10 Correct 4 ms 25060 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 4 ms 25116 KB Output is correct
14 Correct 4 ms 24920 KB Output is correct
15 Correct 4 ms 25176 KB Output is correct
16 Correct 5 ms 24928 KB Output is correct
17 Correct 4 ms 25052 KB Output is correct
18 Correct 6 ms 25708 KB Output is correct
19 Correct 6 ms 25736 KB Output is correct
20 Correct 6 ms 25552 KB Output is correct
21 Correct 8 ms 25696 KB Output is correct
22 Correct 7 ms 25952 KB Output is correct
23 Correct 7 ms 25696 KB Output is correct
24 Correct 7 ms 25700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25308 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24920 KB Output is correct
4 Correct 4 ms 24924 KB Output is correct
5 Correct 3 ms 24924 KB Output is correct
6 Correct 3 ms 24924 KB Output is correct
7 Correct 4 ms 25064 KB Output is correct
8 Correct 4 ms 24924 KB Output is correct
9 Correct 4 ms 24924 KB Output is correct
10 Correct 4 ms 25060 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 4 ms 25116 KB Output is correct
14 Correct 4 ms 24920 KB Output is correct
15 Correct 4 ms 25176 KB Output is correct
16 Correct 5 ms 24928 KB Output is correct
17 Correct 4 ms 25052 KB Output is correct
18 Correct 6 ms 25708 KB Output is correct
19 Correct 6 ms 25736 KB Output is correct
20 Correct 6 ms 25552 KB Output is correct
21 Correct 8 ms 25696 KB Output is correct
22 Correct 7 ms 25952 KB Output is correct
23 Correct 7 ms 25696 KB Output is correct
24 Correct 7 ms 25700 KB Output is correct
25 Correct 4 ms 24920 KB Output is correct
26 Correct 6 ms 25436 KB Output is correct
27 Correct 7 ms 25432 KB Output is correct
28 Correct 7 ms 25532 KB Output is correct
29 Correct 6 ms 25580 KB Output is correct
30 Correct 7 ms 25176 KB Output is correct
31 Correct 6 ms 25328 KB Output is correct
32 Correct 6 ms 25176 KB Output is correct
33 Correct 6 ms 25176 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25308 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24920 KB Output is correct
4 Correct 4 ms 24924 KB Output is correct
5 Correct 3 ms 24924 KB Output is correct
6 Correct 3 ms 24924 KB Output is correct
7 Correct 4 ms 25064 KB Output is correct
8 Correct 4 ms 24924 KB Output is correct
9 Correct 4 ms 24924 KB Output is correct
10 Correct 4 ms 25060 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 4 ms 25116 KB Output is correct
14 Correct 4 ms 24920 KB Output is correct
15 Correct 4 ms 25176 KB Output is correct
16 Correct 5 ms 24928 KB Output is correct
17 Correct 4 ms 25052 KB Output is correct
18 Correct 6 ms 25708 KB Output is correct
19 Correct 6 ms 25736 KB Output is correct
20 Correct 6 ms 25552 KB Output is correct
21 Correct 8 ms 25696 KB Output is correct
22 Correct 7 ms 25952 KB Output is correct
23 Correct 7 ms 25696 KB Output is correct
24 Correct 7 ms 25700 KB Output is correct
25 Incorrect 122 ms 52032 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 4 ms 24924 KB Output is correct
2 Correct 4 ms 25104 KB Output is correct
3 Correct 262 ms 36408 KB Output is correct
4 Correct 219 ms 36304 KB Output is correct
5 Correct 237 ms 36404 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25308 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 4 ms 24920 KB Output is correct
4 Correct 4 ms 24924 KB Output is correct
5 Correct 3 ms 24924 KB Output is correct
6 Correct 3 ms 24924 KB Output is correct
7 Correct 4 ms 25064 KB Output is correct
8 Correct 4 ms 24924 KB Output is correct
9 Correct 4 ms 24924 KB Output is correct
10 Correct 4 ms 25060 KB Output is correct
11 Correct 4 ms 24924 KB Output is correct
12 Correct 4 ms 24924 KB Output is correct
13 Correct 4 ms 25116 KB Output is correct
14 Correct 4 ms 24920 KB Output is correct
15 Correct 4 ms 25176 KB Output is correct
16 Correct 5 ms 24928 KB Output is correct
17 Correct 4 ms 25052 KB Output is correct
18 Correct 6 ms 25708 KB Output is correct
19 Correct 6 ms 25736 KB Output is correct
20 Correct 6 ms 25552 KB Output is correct
21 Correct 8 ms 25696 KB Output is correct
22 Correct 7 ms 25952 KB Output is correct
23 Correct 7 ms 25696 KB Output is correct
24 Correct 7 ms 25700 KB Output is correct
25 Correct 4 ms 24920 KB Output is correct
26 Correct 6 ms 25436 KB Output is correct
27 Correct 7 ms 25432 KB Output is correct
28 Correct 7 ms 25532 KB Output is correct
29 Correct 6 ms 25580 KB Output is correct
30 Correct 7 ms 25176 KB Output is correct
31 Correct 6 ms 25328 KB Output is correct
32 Correct 6 ms 25176 KB Output is correct
33 Correct 6 ms 25176 KB Output is correct
34 Incorrect 122 ms 52032 KB Output isn't correct
35 Halted 0 ms 0 KB -