Submission #930353

#	Time	Username	Problem	Language	Result	Execution time	Memory
930353		koukirocks	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	308 ms	70228 KiB

Main

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

ll n;
ll p[MAX];
ll pid[MAX];
vector<int> G[MAX];
ll dp[MAX];
ll mx[MAX];
ll sz[MAX];
ll fa[MAX];

void init() {
	for (int i=1;i<=n;i++) {
		fa[i]=i;
		sz[i]=1;
		mx[i]=p[i];
	}
}

int get(int a) {
	return fa[a]=(fa[a]==a?a:get(fa[a]));
}

void unionn(int a,int b) {
	a=get(a);b=get(b);
	if (a==b) return;
	if (sz[a]>sz[b]) swap(a,b);
	fa[a]=b;
	sz[b]+=sz[a];
	mx[b]=max(mx[b],mx[a]);
}

ll up[MAX][20];
ll dep[MAX];

void dfs(int v,int p) {
	up[v][0]=p;
	for (int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
	for (int i:G[v]) {
		if (i==p) continue;
		dep[i]=dep[v]+1;
		dfs(i,v);
	}
}

int jump(int v,int k) {
	for (int i=19;i>=0;i--) {
//		cout<<v<<" "<<k<<" "<<i<<"\n";
		if (k&(1<<i)) v=up[v][i];
	}
//	cout<<v<<" fin\n";
	return v;
}

ll dis(int a,int b) {
//	cout<<a<<" "<<b<<" start\n";
//	cout<<dep[a]<<" "<<dep[b]<<" dep\n";
	if (dep[a]<dep[b]) swap(a,b);
	ll ans=dep[a]-dep[b];
	a=jump(a,dep[a]-dep[b]);
//	cout<<a<<" "<<b<<" "<<ans<<"\n";;
	if (a==b) return ans;
	for (int i=19;i>=0;i--) {
		if (up[a][i]!=up[b][i]) {
			a=up[a][i];b=up[b][i];
			ans+=2*(1<<i);
		}
	}
	return ans+2;
}

int main() {
	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>p[i];
		pid[p[i]]=i;
	}
	for (int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	init();
	for (int i=0;i<20;i++) up[0][i]=0;
	dep[1]=0;
	dfs(1,0);
	dp[1]=0;
	for (int i=2;i<=n;i++) {
		ll v=pid[i];
		dp[i]=0;
		for (int u:G[v]) {
			if (p[u]<i) {
				dp[i]=max(dp[i],dp[mx[get(u)]]+dis(pid[mx[get(u)]],v));
//				cout<<pid[mx[get(u)]]<<" "<<v<<" "<<dis(pid[mx[get(u)]],v)<<"\n";
				unionn(u,v);
			}
		}
//		for (int i=1;i<=n;i++) cout<<p[i]<<" ";
//		cout<<"\n";
	}
//	for (int i=1;i<=n;i++) cout<<dp[i]<<" ";
//	cout<<"\n";
	cout<<dp[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