oj.uz

Submission #861475

# Submission time Handle Problem Language Result Execution time Memory
861475 2023-10-16T09:46:30 Z NotLinux Cat Exercise (JOI23_ho_t4) C++17
21 / 100
 111 ms 40708 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
const int M = 20;
int n,p[N],lift[N][M],depth[N];
vector < int > tree[N];
pair < int , int > ord[N];
inline void dfs(int node , int par , int dpt){
	lift[node][0] = par;
	depth[node] = dpt;
	for(int i = 0;i<(int)tree[node].size();i++){
		if(par != tree[node][i]){
			dfs(tree[node][i],node,dpt+1);
		}
	}
}
inline int lca(int a , int b){
	if(depth[a] > depth[b])swap(a,b);
	int diff = depth[b] - depth[a];
	for(int i = 0;i<M;i++){
		if((diff >> i) & 1){
			b = lift[b][i];
		}
	}
	if(a == b)return a;
	for(int i = 0;i<M;i++){
		if(lift[a][i] != lift[b][i]){
			a = lift[a][i];
			b = lift[b][i];
		}
	}
	return lift[a][0];
}
inline int dist(int a , int b){
	return depth[a] + depth[b] - 2 * depth[lca(a,b)];
}
struct DSU{
	vector < int > par,dp;
	DSU(int x){
		x += 3;
		par.resize(x);
		iota(par.begin() , par.end() , 0);
		dp.assign(x,0);
	}
	int find(int a){
		if(par[a] == a)return a;
		return par[a] = find(par[a]);
	}
	void merge(int a , int b){//a -> b
		a = find(a) , b = find(b);
		dp[b] = max(dp[b] , dp[a] + dist(a,b) );
		par[a] = b;
	}
} dsu(N);
void solve(){
	cin >> n;
	for(int i = 0;i<n;i++){
		cin >> p[i];
		ord[i] = {p[i],i};
	}
	sort(ord , ord + n);
	for(int i = 1;i<n;i++){
		int ai,bi;cin >> ai >> bi;
		ai--;bi--;
		tree[ai].push_back(bi);
		tree[bi].push_back(ai);
	}
	//calculating lca
	dfs(0,0,0);
	for(int i = 1;i<M;i++){
		for(int j = 0;j<n;j++){
			lift[j][i] = lift[lift[j][i-1]][i-1];
		}
	}
	int ans = 0;
	for(int i = 0;i<n;i++){
		for(auto itr : tree[ord[i].second]){
			if(p[itr] < ord[i].first){
				dsu.merge(itr , ord[i].second);
			}
		}
		ans = max(ans , dsu.dp[ord[i].second]);
	}
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 2 ms 12304 KB Output is correct
5 Correct 2 ms 12124 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 2 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 12124 KB Output is correct
11 Correct 2 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 3 ms 12120 KB Output is correct
14 Correct 3 ms 12120 KB Output is correct
15 Correct 2 ms 12124 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12304 KB Output is correct
18 Correct 6 ms 12636 KB Output is correct
19 Correct 5 ms 12576 KB Output is correct
20 Correct 4 ms 12636 KB Output is correct
21 Correct 5 ms 12636 KB Output is correct
22 Correct 4 ms 12636 KB Output is correct
23 Correct 4 ms 12636 KB Output is correct
24 Correct 4 ms 12636 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 2 ms 12304 KB Output is correct
5 Correct 2 ms 12124 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 2 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 12124 KB Output is correct
11 Correct 2 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 3 ms 12120 KB Output is correct
14 Correct 3 ms 12120 KB Output is correct
15 Correct 2 ms 12124 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12304 KB Output is correct
18 Correct 6 ms 12636 KB Output is correct
19 Correct 5 ms 12576 KB Output is correct
20 Correct 4 ms 12636 KB Output is correct
21 Correct 5 ms 12636 KB Output is correct
22 Correct 4 ms 12636 KB Output is correct
23 Correct 4 ms 12636 KB Output is correct
24 Correct 4 ms 12636 KB Output is correct
25 Correct 3 ms 12120 KB Output is correct
26 Incorrect 5 ms 12636 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 2 ms 12304 KB Output is correct
5 Correct 2 ms 12124 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 2 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 12124 KB Output is correct
11 Correct 2 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 3 ms 12120 KB Output is correct
14 Correct 3 ms 12120 KB Output is correct
15 Correct 2 ms 12124 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12304 KB Output is correct
18 Correct 6 ms 12636 KB Output is correct
19 Correct 5 ms 12576 KB Output is correct
20 Correct 4 ms 12636 KB Output is correct
21 Correct 5 ms 12636 KB Output is correct
22 Correct 4 ms 12636 KB Output is correct
23 Correct 4 ms 12636 KB Output is correct
24 Correct 4 ms 12636 KB Output is correct
25 Incorrect 111 ms 40708 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Incorrect 2 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 2 ms 12304 KB Output is correct
5 Correct 2 ms 12124 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 2 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 12124 KB Output is correct
11 Correct 2 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 3 ms 12120 KB Output is correct
14 Correct 3 ms 12120 KB Output is correct
15 Correct 2 ms 12124 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12304 KB Output is correct
18 Correct 6 ms 12636 KB Output is correct
19 Correct 5 ms 12576 KB Output is correct
20 Correct 4 ms 12636 KB Output is correct
21 Correct 5 ms 12636 KB Output is correct
22 Correct 4 ms 12636 KB Output is correct
23 Correct 4 ms 12636 KB Output is correct
24 Correct 4 ms 12636 KB Output is correct
25 Correct 3 ms 12120 KB Output is correct
26 Incorrect 5 ms 12636 KB Output isn't correct
27 Halted 0 ms 0 KB -