oj.uz

Submission #911356

# Submission time Handle Problem Language Result Execution time Memory
911356 2024-01-18T19:59:28 Z OAleksa Cat Exercise (JOI23_ho_t4) C++14
31 / 100
 2000 ms 66300 KB 
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 18;
int up[N][K], tin[N], tout[N], timer, dep[N];
int st[4 * N];
int n, a[N], vis[N], bst[N];
vector<int> g[N];
void modify(int v, int tl, int tr, int p, int x) {
	if (tl == tr) {
		st[v] = p;
	}
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			modify(v * 2, tl, mid, p, x);
		else
			modify(v * 2 + 1, mid + 1, tr, p, x);
		if (a[st[v * 2]] > a[st[v * 2 + 1]])
			st[v] = st[v * 2];
		else
			st[v] = st[v * 2 + 1];
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return max(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
	}
}
bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
void dfs(int v, int p) {
	up[v][0] = p;
	tin[v] = ++timer;
	dep[v] = dep[p] + 1;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	bst[v] = v;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
		if (a[bst[u]] > a[bst[v]]) 
			bst[v] = bst[u];
	}
	tout[v] = timer;
}
int Lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
int distance(int a, int b) {
	int lc = Lca(a, b);
	return dep[a] + dep[b] - 2 * dep[lc];
}
pair<int, int> find_mx(int v, int p) {
	if (vis[v]) 
		return {0, 0};
	int mx = a[v], s = v;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		auto x = find_mx(u, v);
		if (x.f > mx) {
			mx = x.f;
			s = x.s;
		}
	}
	return {mx, s};
}
int solve(int x, int p) {
	int v = find_mx(x, 0).s;
	vis[v] = 1;
	int res = 0;
	for (auto u : g[v]) {
		if (vis[u])
			continue;
		res = max(res, solve(u, v));
	}
	return res + distance(v, p);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
  	for (int i = 1;i <= n;i++)	
  		cin >> a[i];
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		g[a].push_back(b);
  		g[b].push_back(a);
  	}
  	int mx = 1;
  	for (int i = 2;i <= n;i++) {
  		if (a[i] > a[mx])
  			mx = i;
  	}
  	dfs(1, 0);
  	cout << solve(mx, mx) << '\n';
	}
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12940 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12940 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12940 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 77 ms 15616 KB Output is correct
19 Correct 69 ms 15448 KB Output is correct
20 Correct 68 ms 15452 KB Output is correct
21 Correct 5 ms 15452 KB Output is correct
22 Correct 6 ms 15460 KB Output is correct
23 Correct 6 ms 15416 KB Output is correct
24 Correct 5 ms 15452 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12940 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 77 ms 15616 KB Output is correct
19 Correct 69 ms 15448 KB Output is correct
20 Correct 68 ms 15452 KB Output is correct
21 Correct 5 ms 15452 KB Output is correct
22 Correct 6 ms 15460 KB Output is correct
23 Correct 6 ms 15416 KB Output is correct
24 Correct 5 ms 15452 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 84 ms 15452 KB Output is correct
27 Correct 79 ms 15452 KB Output is correct
28 Correct 84 ms 15448 KB Output is correct
29 Correct 80 ms 15580 KB Output is correct
30 Correct 9 ms 15196 KB Output is correct
31 Correct 14 ms 15192 KB Output is correct
32 Correct 10 ms 15452 KB Output is correct
33 Correct 13 ms 15356 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12940 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 77 ms 15616 KB Output is correct
19 Correct 69 ms 15448 KB Output is correct
20 Correct 68 ms 15452 KB Output is correct
21 Correct 5 ms 15452 KB Output is correct
22 Correct 6 ms 15460 KB Output is correct
23 Correct 6 ms 15416 KB Output is correct
24 Correct 5 ms 15452 KB Output is correct
25 Execution timed out 2048 ms 66300 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Execution timed out 2078 ms 55424 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12940 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 77 ms 15616 KB Output is correct
19 Correct 69 ms 15448 KB Output is correct
20 Correct 68 ms 15452 KB Output is correct
21 Correct 5 ms 15452 KB Output is correct
22 Correct 6 ms 15460 KB Output is correct
23 Correct 6 ms 15416 KB Output is correct
24 Correct 5 ms 15452 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 84 ms 15452 KB Output is correct
27 Correct 79 ms 15452 KB Output is correct
28 Correct 84 ms 15448 KB Output is correct
29 Correct 80 ms 15580 KB Output is correct
30 Correct 9 ms 15196 KB Output is correct
31 Correct 14 ms 15192 KB Output is correct
32 Correct 10 ms 15452 KB Output is correct
33 Correct 13 ms 15356 KB Output is correct
34 Execution timed out 2048 ms 66300 KB Time limit exceeded
35 Halted 0 ms 0 KB -