제출 #946352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946352		djs100201	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	235 ms	64772 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =2e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
vector<ll>v[n_];
ll arr[n_],parent[n_][21],dep[n_],par[n_],dp[n_];
ll find(ll x){
	if(par[x]<0)return x;
	return par[x]=find(par[x]);
}
void merge(ll x,ll y){
	x=find(x),y=find(y);
	if(x==y)return;
	par[x]=y;
}
void dfs(int x, int par) {
	dep[x] = dep[par] + 1;
	for (int nxt : v[x]) {
		if (nxt == par)continue;
		parent[nxt][0] = x;
		dfs(nxt, x);
	}
}
int lca(int x, int y) {
	if (dep[x] > dep[y])swap(x, y);//항상 y의 depth가 더 깊게 만들어주자!
	for (int i = 20; i >= 0; i--)
		if (dep[y] - dep[x] >= (1 << i))
			y = parent[y][i];
	if (x == y)return x;
	for (int i = 20; i >= 0; i--) {
		if (parent[x][i] != parent[y][i]) {
			x = parent[x][i];
			y = parent[y][i];
		}
	}
	return parent[x][0];
}
ll dist(ll x,ll y){
	ll z=lca(x,y);
	return dep[x]-dep[z]+dep[y]-dep[z];
}
void solve(){
	cin>>n;
	vector<P>A;
	for(int i=1;i<=n;i++)cin>>arr[i],A.push_back({arr[i],i});
	sort(all(A));
	for(int i=1;i<n;i++){
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1,0);
	for (int i = 1; i < 21; i++)
		for (int j = 1; j <= n; j++)
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
	memset(par,-1,sizeof(par));
	for(auto [a,b]:A){
		ll ret=0;
		for(auto nxt:v[b]){
			if(arr[nxt]>a)continue;
			x=find(nxt);
			ret=max(ret,dp[x]+dist(x,b));
			merge(x,b);
		}
		dp[b]=ret;
		//cout<<b<<' '<<dp[b]<<endl;
	}
	cout<<dp[A.back().second]<<endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);  
	//cin >> tc;
	while (tc--)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