답안 #911397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911397	2024-01-18T21:08:38 Z	OAleksa	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	485 ms	76228 KB

Main

#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], act[4 * N];
int n, a[N], vis[N];
vector<int> g[N];
void modify(int v, int tl, int tr, int p, int x) {
	if (tl == tr) {
		st[v] = x;
	}
	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 || act[v])
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		int left = get(v * 2, tl, mid, l, r);
		int right = get(v * 2 + 1, mid + 1, tr, l, r);
		if (a[left] > a[right])
			return left;
		return right;
	}
}
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];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	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) {
	if (a == 0 || b == 0)
		return 0;
	int lc = Lca(a, b);
	return dep[a] + dep[b] - 2 * dep[lc];
}

void activate(int v, int tl, int tr, int l, int r, int x) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r)
		act[v] = x;
	else {
		int mid = (tl + tr) / 2;
		activate(v * 2, tl, mid, l, r, x);
		activate(v * 2 + 1, mid + 1, tr, l, r, x);
		if (act[v * 2] == 1 && act[v * 2 + 1] == 1)
			st[v] = 0;
		else if (act[v * 2] == 1 && act[v * 2 + 1] == 0)
			st[v] = st[v * 2 + 1];
		else if (act[v * 2] == 0 && act[v * 2 + 1] == 1) {
			st[v] = st[v * 2];
		}
		else {
			if (a[st[v * 2]] > a[st[v * 2 + 1]])
				st[v] = st[v * 2];
			else
				st[v] = st[v * 2 + 1];
		}
	}
}
int solve(int x, int p) {
	int v = get(1, 1, n, tin[x], tout[x]);
	vis[v] = 1;
	int res = 0;
	int s = -1;
	for (auto u : g[v]) {
		if (vis[u])
			continue;
		if (dep[u] > dep[v]) 
			res = max(res, solve(u, v));	
		else {
			s = u;
			// activate(1, 1, n, tin[v], tout[v], 1);
			// res = max(res, solve(x, v));
			// activate(1, 1, n, tin[v], tout[v], 0);
		}
	}
	if (s != -1) {
		activate(1, 1, n, tin[v], tout[v], 1);
		res = max(res, solve(x, v));
		activate(1, 1, n, tin[v], tout[v], 0);
	}
	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);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= n;i++)
  		modify(1, 1, n, tin[i], i);
  	cout << solve(1, 0) << '\n';
	}
  return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	3 ms	14940 KB	Output is correct
4	Correct	3 ms	14940 KB	Output is correct
5	Correct	3 ms	14940 KB	Output is correct
6	Correct	3 ms	14940 KB	Output is correct
7	Correct	3 ms	14940 KB	Output is correct
8	Correct	3 ms	15192 KB	Output is correct
9	Correct	3 ms	15192 KB	Output is correct
10	Correct	3 ms	14988 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	3 ms	14940 KB	Output is correct
4	Correct	3 ms	14940 KB	Output is correct
5	Correct	3 ms	14940 KB	Output is correct
6	Correct	3 ms	14940 KB	Output is correct
7	Correct	3 ms	14940 KB	Output is correct
8	Correct	3 ms	15192 KB	Output is correct
9	Correct	3 ms	15192 KB	Output is correct
10	Correct	3 ms	14988 KB	Output is correct
11	Correct	3 ms	14940 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14940 KB	Output is correct
15	Correct	3 ms	14940 KB	Output is correct
16	Correct	3 ms	14940 KB	Output is correct
17	Correct	3 ms	14940 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	3 ms	14940 KB	Output is correct
4	Correct	3 ms	14940 KB	Output is correct
5	Correct	3 ms	14940 KB	Output is correct
6	Correct	3 ms	14940 KB	Output is correct
7	Correct	3 ms	14940 KB	Output is correct
8	Correct	3 ms	15192 KB	Output is correct
9	Correct	3 ms	15192 KB	Output is correct
10	Correct	3 ms	14988 KB	Output is correct
11	Correct	3 ms	14940 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14940 KB	Output is correct
15	Correct	3 ms	14940 KB	Output is correct
16	Correct	3 ms	14940 KB	Output is correct
17	Correct	3 ms	14940 KB	Output is correct
18	Correct	6 ms	15452 KB	Output is correct
19	Correct	7 ms	15452 KB	Output is correct
20	Correct	6 ms	15448 KB	Output is correct
21	Correct	7 ms	15452 KB	Output is correct
22	Correct	6 ms	15448 KB	Output is correct
23	Correct	6 ms	15452 KB	Output is correct
24	Correct	7 ms	15252 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	3 ms	14940 KB	Output is correct
4	Correct	3 ms	14940 KB	Output is correct
5	Correct	3 ms	14940 KB	Output is correct
6	Correct	3 ms	14940 KB	Output is correct
7	Correct	3 ms	14940 KB	Output is correct
8	Correct	3 ms	15192 KB	Output is correct
9	Correct	3 ms	15192 KB	Output is correct
10	Correct	3 ms	14988 KB	Output is correct
11	Correct	3 ms	14940 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14940 KB	Output is correct
15	Correct	3 ms	14940 KB	Output is correct
16	Correct	3 ms	14940 KB	Output is correct
17	Correct	3 ms	14940 KB	Output is correct
18	Correct	6 ms	15452 KB	Output is correct
19	Correct	7 ms	15452 KB	Output is correct
20	Correct	6 ms	15448 KB	Output is correct
21	Correct	7 ms	15452 KB	Output is correct
22	Correct	6 ms	15448 KB	Output is correct
23	Correct	6 ms	15452 KB	Output is correct
24	Correct	7 ms	15252 KB	Output is correct
25	Correct	4 ms	14940 KB	Output is correct
26	Correct	7 ms	15452 KB	Output is correct
27	Correct	7 ms	15452 KB	Output is correct
28	Correct	8 ms	15452 KB	Output is correct
29	Correct	9 ms	15452 KB	Output is correct
30	Correct	7 ms	15196 KB	Output is correct
31	Correct	7 ms	15192 KB	Output is correct
32	Correct	7 ms	15196 KB	Output is correct
33	Correct	7 ms	15196 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	3 ms	14940 KB	Output is correct
4	Correct	3 ms	14940 KB	Output is correct
5	Correct	3 ms	14940 KB	Output is correct
6	Correct	3 ms	14940 KB	Output is correct
7	Correct	3 ms	14940 KB	Output is correct
8	Correct	3 ms	15192 KB	Output is correct
9	Correct	3 ms	15192 KB	Output is correct
10	Correct	3 ms	14988 KB	Output is correct
11	Correct	3 ms	14940 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14940 KB	Output is correct
15	Correct	3 ms	14940 KB	Output is correct
16	Correct	3 ms	14940 KB	Output is correct
17	Correct	3 ms	14940 KB	Output is correct
18	Correct	6 ms	15452 KB	Output is correct
19	Correct	7 ms	15452 KB	Output is correct
20	Correct	6 ms	15448 KB	Output is correct
21	Correct	7 ms	15452 KB	Output is correct
22	Correct	6 ms	15448 KB	Output is correct
23	Correct	6 ms	15452 KB	Output is correct
24	Correct	7 ms	15252 KB	Output is correct
25	Correct	169 ms	72476 KB	Output is correct
26	Correct	181 ms	76228 KB	Output is correct
27	Correct	176 ms	76116 KB	Output is correct
28	Correct	180 ms	70852 KB	Output is correct
29	Correct	179 ms	70836 KB	Output is correct
30	Correct	185 ms	70692 KB	Output is correct
31	Correct	177 ms	70744 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14940 KB	Output is correct
2	Correct	3 ms	14984 KB	Output is correct
3	Correct	223 ms	60296 KB	Output is correct
4	Correct	226 ms	64084 KB	Output is correct
5	Correct	221 ms	64484 KB	Output is correct

Subtask #7
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	14936 KB	Output is correct
2	Correct	4 ms	14936 KB	Output is correct
3	Correct	3 ms	14940 KB	Output is correct
4	Correct	3 ms	14940 KB	Output is correct
5	Correct	3 ms	14940 KB	Output is correct
6	Correct	3 ms	14940 KB	Output is correct
7	Correct	3 ms	14940 KB	Output is correct
8	Correct	3 ms	15192 KB	Output is correct
9	Correct	3 ms	15192 KB	Output is correct
10	Correct	3 ms	14988 KB	Output is correct
11	Correct	3 ms	14940 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14940 KB	Output is correct
15	Correct	3 ms	14940 KB	Output is correct
16	Correct	3 ms	14940 KB	Output is correct
17	Correct	3 ms	14940 KB	Output is correct
18	Correct	6 ms	15452 KB	Output is correct
19	Correct	7 ms	15452 KB	Output is correct
20	Correct	6 ms	15448 KB	Output is correct
21	Correct	7 ms	15452 KB	Output is correct
22	Correct	6 ms	15448 KB	Output is correct
23	Correct	6 ms	15452 KB	Output is correct
24	Correct	7 ms	15252 KB	Output is correct
25	Correct	4 ms	14940 KB	Output is correct
26	Correct	7 ms	15452 KB	Output is correct
27	Correct	7 ms	15452 KB	Output is correct
28	Correct	8 ms	15452 KB	Output is correct
29	Correct	9 ms	15452 KB	Output is correct
30	Correct	7 ms	15196 KB	Output is correct
31	Correct	7 ms	15192 KB	Output is correct
32	Correct	7 ms	15196 KB	Output is correct
33	Correct	7 ms	15196 KB	Output is correct
34	Correct	169 ms	72476 KB	Output is correct
35	Correct	181 ms	76228 KB	Output is correct
36	Correct	176 ms	76116 KB	Output is correct
37	Correct	180 ms	70852 KB	Output is correct
38	Correct	179 ms	70836 KB	Output is correct
39	Correct	185 ms	70692 KB	Output is correct
40	Correct	177 ms	70744 KB	Output is correct
41	Correct	3 ms	14940 KB	Output is correct
42	Correct	3 ms	14984 KB	Output is correct
43	Correct	223 ms	60296 KB	Output is correct
44	Correct	226 ms	64084 KB	Output is correct
45	Correct	221 ms	64484 KB	Output is correct
46	Correct	485 ms	72388 KB	Output is correct
47	Correct	417 ms	72532 KB	Output is correct
48	Correct	441 ms	72636 KB	Output is correct
49	Correct	436 ms	73044 KB	Output is correct
50	Correct	367 ms	62656 KB	Output is correct
51	Correct	379 ms	63572 KB	Output is correct
52	Correct	378 ms	62648 KB	Output is correct
53	Correct	372 ms	63060 KB	Output is correct

답안 #911397

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 20.0 / 20.0

Subtask #6 23.0 / 23.0

Subtask #7 26.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
20.0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
26.0 / 26.0