oj.uz

Submission #1032010

# Submission time Handle Problem Language Result Execution time Memory
1032010 2024-07-23T09:57:00 Z ten_xd Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 239 ms 62544 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int N = 5e5+5, LG = 18, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

struct Node
{
	int v, val;
	bool operator < (const Node &node) const
	{
		return val < node.val;
	}
};

int n,cnt,base,rozmiar_drzewa;
int A[N];
vector<int> G[N];
bool vis[N];
int pre[N];
int siz[N];
int P[N];
int deg[N];
vector<Node> tree;
int skok[LG+1][N];

void DFS(int v, int par)
{
	siz[v] = 1, pre[v] = ++cnt, P[v] = par, tree[cnt+base] = {v,A[v]};
	for(auto x : G[v])
	{
		if(x == par) continue;
		deg[x] = deg[v] + 1, DFS(x,v), siz[v] += siz[x];
	}
}

Node query(int l, int p)
{
	l = l + base - 1, p = p + base + 1;
	Node res = {-1,-1};
	while(l/2 != p/2)
	{
		if(l % 2 == 0) res = max(res,tree[l+1]);
		if(p % 2 == 1) res = max(res,tree[p-1]);
		l /= 2, p /= 2;
	}
	return res;
}

void update(int v, Node val)
{
	v += base, tree[v] = val, v /= 2;
	while(v > 0) tree[v] = max(tree[v*2],tree[v*2+1]), v /= 2;
}

int LCA(int x, int y)
{
	if(deg[x] < deg[y]) swap(x,y);
	for(int i = LG; i >= 0; --i)
	{
		int v = skok[i][x];
		if(deg[v] >= deg[y]) x = v;
	}

	if(x == y) return x;
	for(int i = LG; i >= 0; --i)
	{
		int vx = skok[i][x], vy = skok[i][y];
		if(vx != vy) x = vx, y = vy;
	}
	return skok[0][x];
}

int odl(int a, int b)
{
	return deg[a] + deg[b] - 2*deg[LCA(a,b)];
}

ll DFS2(int v, int b)
{
	vis[v] = 1;
	ll val = 0;
	update(pre[v],{-1,-1});
	for(auto x : G[v])
	{
		if(vis[x]) continue;
		if(deg[x] > deg[v])
		{
			Node akt = query(pre[x],pre[x]+siz[x]-1);
			val = max(val,(ll)odl(v,akt.v)+DFS2(akt.v,x));
		}
	}
	if(v != b)
	{
		Node akt = query(pre[b],pre[b]+siz[b]-1);
		val = max(val,(ll)odl(v,akt.v)+DFS2(akt.v,b));
	}
	return val;
}

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> A[i];
	rep(i,n-1)
	{
		int a,b;
		cin >> a >> b;
		G[a].pb(b), G[b].pb(a);
	}

	base = 1;
	while(base <= n+5) base *= 2;
	rozmiar_drzewa = base * 2;
	tree.assign(rozmiar_drzewa,{-1,-1});

	deg[1] = 1, DFS(1,0);
	for(int i = base-1; i >= 1; --i) tree[i] = max(tree[i*2],tree[i*2+1]);

	for(int i = 1; i <= n; ++i) skok[0][i] = P[i];
	for(int i = 1; i <= LG; ++i) for(int v = 1; v <= n; ++v) skok[i][v] = skok[i-1][skok[i-1][v]];

	int wie = 1;
	for(int i = 1; i <= n; ++i) if(A[i] == n) wie = i;
	cout << DFS2(wie,1) << '\n';
}

int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 5 ms 12632 KB Output is correct
6 Correct 4 ms 12324 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 5 ms 12632 KB Output is correct
6 Correct 4 ms 12324 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12636 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12552 KB Output is correct
14 Correct 6 ms 12376 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12608 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 5 ms 12632 KB Output is correct
6 Correct 4 ms 12324 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12636 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12552 KB Output is correct
14 Correct 6 ms 12376 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12608 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 7 ms 13660 KB Output is correct
19 Correct 7 ms 13660 KB Output is correct
20 Correct 6 ms 13660 KB Output is correct
21 Correct 7 ms 13912 KB Output is correct
22 Correct 7 ms 13660 KB Output is correct
23 Correct 7 ms 13660 KB Output is correct
24 Correct 7 ms 13660 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 5 ms 12632 KB Output is correct
6 Correct 4 ms 12324 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12636 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12552 KB Output is correct
14 Correct 6 ms 12376 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12608 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 7 ms 13660 KB Output is correct
19 Correct 7 ms 13660 KB Output is correct
20 Correct 6 ms 13660 KB Output is correct
21 Correct 7 ms 13912 KB Output is correct
22 Correct 7 ms 13660 KB Output is correct
23 Correct 7 ms 13660 KB Output is correct
24 Correct 7 ms 13660 KB Output is correct
25 Correct 6 ms 12376 KB Output is correct
26 Correct 7 ms 13660 KB Output is correct
27 Correct 8 ms 13660 KB Output is correct
28 Correct 8 ms 13528 KB Output is correct
29 Correct 10 ms 13492 KB Output is correct
30 Correct 8 ms 13144 KB Output is correct
31 Correct 7 ms 13148 KB Output is correct
32 Correct 7 ms 13148 KB Output is correct
33 Correct 10 ms 13144 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 5 ms 12632 KB Output is correct
6 Correct 4 ms 12324 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12636 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12552 KB Output is correct
14 Correct 6 ms 12376 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12608 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 7 ms 13660 KB Output is correct
19 Correct 7 ms 13660 KB Output is correct
20 Correct 6 ms 13660 KB Output is correct
21 Correct 7 ms 13912 KB Output is correct
22 Correct 7 ms 13660 KB Output is correct
23 Correct 7 ms 13660 KB Output is correct
24 Correct 7 ms 13660 KB Output is correct
25 Correct 115 ms 60504 KB Output is correct
26 Correct 136 ms 62544 KB Output is correct
27 Correct 140 ms 62544 KB Output is correct
28 Correct 125 ms 61076 KB Output is correct
29 Correct 115 ms 61268 KB Output is correct
30 Correct 115 ms 61264 KB Output is correct
31 Correct 146 ms 61148 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 118 ms 43140 KB Output is correct
4 Correct 108 ms 43316 KB Output is correct
5 Correct 107 ms 43124 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 5 ms 12632 KB Output is correct
6 Correct 4 ms 12324 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12636 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12552 KB Output is correct
14 Correct 6 ms 12376 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12608 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 7 ms 13660 KB Output is correct
19 Correct 7 ms 13660 KB Output is correct
20 Correct 6 ms 13660 KB Output is correct
21 Correct 7 ms 13912 KB Output is correct
22 Correct 7 ms 13660 KB Output is correct
23 Correct 7 ms 13660 KB Output is correct
24 Correct 7 ms 13660 KB Output is correct
25 Correct 6 ms 12376 KB Output is correct
26 Correct 7 ms 13660 KB Output is correct
27 Correct 8 ms 13660 KB Output is correct
28 Correct 8 ms 13528 KB Output is correct
29 Correct 10 ms 13492 KB Output is correct
30 Correct 8 ms 13144 KB Output is correct
31 Correct 7 ms 13148 KB Output is correct
32 Correct 7 ms 13148 KB Output is correct
33 Correct 10 ms 13144 KB Output is correct
34 Correct 115 ms 60504 KB Output is correct
35 Correct 136 ms 62544 KB Output is correct
36 Correct 140 ms 62544 KB Output is correct
37 Correct 125 ms 61076 KB Output is correct
38 Correct 115 ms 61268 KB Output is correct
39 Correct 115 ms 61264 KB Output is correct
40 Correct 146 ms 61148 KB Output is correct
41 Correct 4 ms 12376 KB Output is correct
42 Correct 4 ms 12380 KB Output is correct
43 Correct 118 ms 43140 KB Output is correct
44 Correct 108 ms 43316 KB Output is correct
45 Correct 107 ms 43124 KB Output is correct
46 Correct 236 ms 58648 KB Output is correct
47 Correct 239 ms 58656 KB Output is correct
48 Correct 224 ms 58720 KB Output is correct
49 Correct 218 ms 58680 KB Output is correct
50 Correct 228 ms 45956 KB Output is correct
51 Correct 183 ms 45940 KB Output is correct
52 Correct 169 ms 45924 KB Output is correct
53 Correct 186 ms 45904 KB Output is correct