Submission #833013

#	Time	Username	Problem	Language	Result	Execution time	Memory
833013		beepbeepsheep	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	390 ms	64888 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=2e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll arr[maxn];
ii brr[maxn];
ll par[maxn];
ll dp[maxn];
ll root(ll x){
	if (par[x]==x) return x;
	return par[x]=root(par[x]);
}
void connect(ll a, ll b){
	a=root(a),b=root(b);
	if (arr[a]>arr[b]) swap(a,b);
	par[a]=b;
}
vector<ll> adj[maxn];
ll twok[maxn][22];
ll depth[maxn];
void dfs(ll x, ll p){
	twok[x][0]=p;
	depth[x]=depth[p]+1;
	for (int i=1;i<21;i++){
		ll h=twok[x][i-1];
		twok[x][i]=twok[h][i-1];
	}
	for (auto u:adj[x]){
		if (u==p) continue;
		dfs(u,x);
	}
}
ll lca(ll a, ll b){
	if (depth[a]<depth[b]) swap(a,b);
	for (int i=21;i>=0;i--){
		if (depth[twok[a][i]]>=depth[b]) a=twok[a][i];
	}
	if (a==b) return a;
	for (int i=21;i>=0;i--){
		if (twok[a][i]!=twok[b][i]) a=twok[a][i],b=twok[b][i];
	}
	return twok[a][0];
}
ll dis(ll a, ll b){
	return depth[a]+depth[b]-2*depth[lca(a,b)];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>arr[i];
		brr[i].first=arr[i],brr[i].second=i;
		par[i]=i;
	}
	sort(brr+1,brr+1+n);
	ll a,b;
	for (int i=1;i<n;i++){
		cin>>a>>b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	dfs(1,0);
	for (ll i=1;i<=n;i++){
		ll x=brr[i].second;
		for (auto u:adj[x]){
			if (arr[u]<arr[x]){
				ll u2=root(u);
				dp[x]=max(dp[x],dp[u2]+dis(x,u2));
				connect(u2,x);	
			}
		}
	}
	cout<<dp[brr[n].second];
	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