Submission #986093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986093	2024-05-19T17:54:08 Z	TomkeMonke	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	264 ms	70680 KB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
 
const int MAXN = 2e5 + 7;
const int LOG = 18;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int A = 26;
const int baz = 1<<20;

vector<int> G[MAXN];
int dp[MAXN][LOG];
int weight[MAXN];
int siz[MAXN];
int par[MAXN];
int maks[MAXN];
int pos[MAXN];
int d[MAXN];
int pre[MAXN];
int post[MAXN];
int res[MAXN];
int c = -1;
vector<pii> verts;

typedef long long ll;




int Find(int v){
	
	return (v == par[v] ? v : par[v] = Find(par[v]));
}


void Union(int a, int b){
	
	a = Find(a); b = Find(b);
	if(a == b) return;
	
	if(siz[a] < siz[b]) swap(a, b);	
	
	
	siz[a] += siz[b];
	maks[a] = max(maks[a], maks[b]);
	par[b] = a;
}






void DFS(int v, int p){
	
	dp[v][0] = p;
	pre[v] = ++c;
	
	for(int i = 1; i < LOG; i++){
		
		dp[v][i] = dp[dp[v][i - 1]][i - 1];
	}
	
	for(auto u : G[v]){
		
		if(u == p) continue;
		d[u] = d[v] + 1;
		DFS(u, v);
	}
	
	post[v] = ++c;
}




bool ancestor(int a, int b){
	
	return pre[a] < pre[b] && post[a] > post[b];
}


int lca(int a, int b){
	
	if(ancestor(a, b)) return a;
	if(ancestor(b, a)) return b;
	
	for(int i = LOG - 1; i >= 0; i--){
		
		if(!ancestor(dp[a][i], b)) a = dp[a][i];
	}
	
	return dp[a][0];
}



signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n;
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		
		cin >> weight[i];
		siz[i] = 1;
		par[i] = i;
		maks[i] = weight[i];
		pos[weight[i]] = i;
		verts.push_back({weight[i], i});
	}
	
	sort(verts.begin(), verts.end());
	
	for(int i = 1; i < n; i++){
		
		int a, b;
		cin >> a >> b;
		
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	DFS(1, 1);
	
	for(auto [val, v] : verts){
		
		for(auto u : G[v]){
			
			if(weight[u] < val){
				
				int x = pos[maks[Find(u)]];
				int dist = d[v] + d[x] - 2 * d[lca(v, x)];
				res[v] = max(res[v], res[x] + dist);
				Union(u, v);
			}
		}
		
		if(val == n) cout << res[v] << '\n';
	}
	
	return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	20568 KB	Output is correct
2	Correct	4 ms	20572 KB	Output is correct
3	Correct	4 ms	20572 KB	Output is correct
4	Correct	4 ms	20572 KB	Output is correct
5	Correct	3 ms	20572 KB	Output is correct
6	Correct	4 ms	20572 KB	Output is correct
7	Correct	3 ms	20572 KB	Output is correct
8	Correct	4 ms	20572 KB	Output is correct
9	Correct	4 ms	20572 KB	Output is correct
10	Correct	4 ms	20572 KB	Output is correct
11	Correct	4 ms	20572 KB	Output is correct
12	Correct	4 ms	20572 KB	Output is correct
13	Correct	4 ms	20572 KB	Output is correct
14	Correct	4 ms	20552 KB	Output is correct
15	Correct	3 ms	20572 KB	Output is correct
16	Correct	4 ms	20572 KB	Output is correct
17	Correct	4 ms	20552 KB	Output is correct
18	Correct	6 ms	23128 KB	Output is correct
19	Correct	6 ms	23132 KB	Output is correct
20	Correct	6 ms	23132 KB	Output is correct
21	Correct	6 ms	23132 KB	Output is correct
22	Correct	6 ms	23132 KB	Output is correct
23	Correct	6 ms	23132 KB	Output is correct
24	Correct	6 ms	23128 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	20568 KB	Output is correct
2	Correct	4 ms	20572 KB	Output is correct
3	Correct	4 ms	20572 KB	Output is correct
4	Correct	4 ms	20572 KB	Output is correct
5	Correct	3 ms	20572 KB	Output is correct
6	Correct	4 ms	20572 KB	Output is correct
7	Correct	3 ms	20572 KB	Output is correct
8	Correct	4 ms	20572 KB	Output is correct
9	Correct	4 ms	20572 KB	Output is correct
10	Correct	4 ms	20572 KB	Output is correct
11	Correct	4 ms	20572 KB	Output is correct
12	Correct	4 ms	20572 KB	Output is correct
13	Correct	4 ms	20572 KB	Output is correct
14	Correct	4 ms	20552 KB	Output is correct
15	Correct	3 ms	20572 KB	Output is correct
16	Correct	4 ms	20572 KB	Output is correct
17	Correct	4 ms	20552 KB	Output is correct
18	Correct	6 ms	23128 KB	Output is correct
19	Correct	6 ms	23132 KB	Output is correct
20	Correct	6 ms	23132 KB	Output is correct
21	Correct	6 ms	23132 KB	Output is correct
22	Correct	6 ms	23132 KB	Output is correct
23	Correct	6 ms	23132 KB	Output is correct
24	Correct	6 ms	23128 KB	Output is correct
25	Correct	4 ms	20572 KB	Output is correct
26	Correct	7 ms	22900 KB	Output is correct
27	Correct	6 ms	23132 KB	Output is correct
28	Correct	6 ms	22900 KB	Output is correct
29	Correct	6 ms	23132 KB	Output is correct
30	Correct	7 ms	22876 KB	Output is correct
31	Correct	6 ms	22876 KB	Output is correct
32	Correct	7 ms	23004 KB	Output is correct
33	Correct	7 ms	22872 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	20568 KB	Output is correct
2	Correct	4 ms	20572 KB	Output is correct
3	Correct	4 ms	20572 KB	Output is correct
4	Correct	4 ms	20572 KB	Output is correct
5	Correct	3 ms	20572 KB	Output is correct
6	Correct	4 ms	20572 KB	Output is correct
7	Correct	3 ms	20572 KB	Output is correct
8	Correct	4 ms	20572 KB	Output is correct
9	Correct	4 ms	20572 KB	Output is correct
10	Correct	4 ms	20572 KB	Output is correct
11	Correct	4 ms	20572 KB	Output is correct
12	Correct	4 ms	20572 KB	Output is correct
13	Correct	4 ms	20572 KB	Output is correct
14	Correct	4 ms	20552 KB	Output is correct
15	Correct	3 ms	20572 KB	Output is correct
16	Correct	4 ms	20572 KB	Output is correct
17	Correct	4 ms	20552 KB	Output is correct
18	Correct	6 ms	23128 KB	Output is correct
19	Correct	6 ms	23132 KB	Output is correct
20	Correct	6 ms	23132 KB	Output is correct
21	Correct	6 ms	23132 KB	Output is correct
22	Correct	6 ms	23132 KB	Output is correct
23	Correct	6 ms	23132 KB	Output is correct
24	Correct	6 ms	23128 KB	Output is correct
25	Correct	101 ms	69832 KB	Output is correct
26	Correct	101 ms	69820 KB	Output is correct
27	Correct	99 ms	69732 KB	Output is correct
28	Correct	140 ms	70564 KB	Output is correct
29	Correct	138 ms	69824 KB	Output is correct
30	Correct	147 ms	70680 KB	Output is correct
31	Correct	137 ms	69844 KB	Output is correct

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	20572 KB	Output is correct
2	Correct	3 ms	20572 KB	Output is correct
3	Correct	153 ms	62448 KB	Output is correct
4	Correct	152 ms	61888 KB	Output is correct
5	Correct	151 ms	61884 KB	Output is correct

Subtask #7
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	20568 KB	Output is correct
2	Correct	4 ms	20572 KB	Output is correct
3	Correct	4 ms	20572 KB	Output is correct
4	Correct	4 ms	20572 KB	Output is correct
5	Correct	3 ms	20572 KB	Output is correct
6	Correct	4 ms	20572 KB	Output is correct
7	Correct	3 ms	20572 KB	Output is correct
8	Correct	4 ms	20572 KB	Output is correct
9	Correct	4 ms	20572 KB	Output is correct
10	Correct	4 ms	20572 KB	Output is correct
11	Correct	4 ms	20572 KB	Output is correct
12	Correct	4 ms	20572 KB	Output is correct
13	Correct	4 ms	20572 KB	Output is correct
14	Correct	4 ms	20552 KB	Output is correct
15	Correct	3 ms	20572 KB	Output is correct
16	Correct	4 ms	20572 KB	Output is correct
17	Correct	4 ms	20552 KB	Output is correct
18	Correct	6 ms	23128 KB	Output is correct
19	Correct	6 ms	23132 KB	Output is correct
20	Correct	6 ms	23132 KB	Output is correct
21	Correct	6 ms	23132 KB	Output is correct
22	Correct	6 ms	23132 KB	Output is correct
23	Correct	6 ms	23132 KB	Output is correct
24	Correct	6 ms	23128 KB	Output is correct
25	Correct	4 ms	20572 KB	Output is correct
26	Correct	7 ms	22900 KB	Output is correct
27	Correct	6 ms	23132 KB	Output is correct
28	Correct	6 ms	22900 KB	Output is correct
29	Correct	6 ms	23132 KB	Output is correct
30	Correct	7 ms	22876 KB	Output is correct
31	Correct	6 ms	22876 KB	Output is correct
32	Correct	7 ms	23004 KB	Output is correct
33	Correct	7 ms	22872 KB	Output is correct
34	Correct	101 ms	69832 KB	Output is correct
35	Correct	101 ms	69820 KB	Output is correct
36	Correct	99 ms	69732 KB	Output is correct
37	Correct	140 ms	70564 KB	Output is correct
38	Correct	138 ms	69824 KB	Output is correct
39	Correct	147 ms	70680 KB	Output is correct
40	Correct	137 ms	69844 KB	Output is correct
41	Correct	4 ms	20572 KB	Output is correct
42	Correct	3 ms	20572 KB	Output is correct
43	Correct	153 ms	62448 KB	Output is correct
44	Correct	152 ms	61888 KB	Output is correct
45	Correct	151 ms	61884 KB	Output is correct
46	Correct	257 ms	66240 KB	Output is correct
47	Correct	263 ms	66144 KB	Output is correct
48	Correct	235 ms	66512 KB	Output is correct
49	Correct	264 ms	65472 KB	Output is correct
50	Correct	253 ms	62504 KB	Output is correct
51	Correct	236 ms	61628 KB	Output is correct
52	Correct	248 ms	61464 KB	Output is correct
53	Correct	232 ms	61632 KB	Output is correct

Submission #986093

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