Submission #986093

#	Time	Username	Problem	Language	Result	Execution time	Memory
986093		TomkeMonke	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	264 ms	70680 KiB

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