Submission #861487

#	Time	Username	Problem	Language	Result	Execution time	Memory
861487		NotLinux	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	267 ms	77320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
const int M = 30;
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 = M-1;i>=0;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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26