Submission #1095455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095455		Abito	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	559 ms	212052 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=4e5+5;
int n,f[N],par[N],dp[N],dep[N],lg[N],t;
pair<int,int> a[N],st[20][N];
set<pair<int,int>> s[N];
vector<int> adj1[N],adj2[N];
void dfs(int x,int p){
	t++;
	f[x]=t;
	dep[x]=dep[p]+1;
	st[0][t]={dep[x],x};
	for (auto u:adj1[x]){
		if (u==p) continue;
		dfs(u,x);
		st[0][++t]={dep[x],x};
	}return;
}
void build(){
	for (int i=1;i<20;i++) for (int j=1;j+(1<<i)<=2*n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	return;
}
int LCA(int x,int y){
	int l=f[x],r=f[y];
	if (l>r) swap(l,r);
	int i=lg[r-l+1];
	return min(st[i][l],st[i][r-(1<<i)+1]).S;
}
int dis(int x,int y){
	return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
int getpar(int x){
	if (x==par[x]) return x;
	return par[x]=getpar(par[x]);
}
void link(int x,int y){
	x=getpar(x);y=getpar(y);
	if (x==y) return;
	if (s[x].size()>s[y].size()) swap(x,y);
	for (auto u:s[x]) s[y].ep(u);
	par[x]=y;
	return;
}
void dfs1(int x,int p){
	for (auto u:adj2[x]){
		if (u==p) continue;
		dfs1(u,x);
		dp[x]=max(dp[x],dp[u]+dis(x,u));
	}return;
}
int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	for (int i=2;i<N;i++) lg[i]=lg[i/2]+1;
	cin>>n;int r=0;
	for (int i=1;i<=n;i++){
		cin>>a[i].F;
		a[i].S=i;
		if (a[i].F==n) r=i;
		par[i]=i;
	}
	for (int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		adj1[x].pb(y);
		adj1[y].pb(x);
		s[x].ep({a[y].F,y});
		s[y].ep({a[x].F,x});
	}
	dfs(1,0);
	build();
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++){
		int x=getpar(a[i].S);
		while (!s[x].empty()){
			pair<int,int> y=*s[x].begin();
			s[x].erase(y);
			if (getpar(y.S)==x) continue;
			//cout<<a[i].S<<' '<<y.S<<endl;
			link(x,y.S);
			adj2[a[i].S].pb(y.S);
			adj2[y.S].pb(a[i].S);
			break;
		}
	}
	dfs1(r,0);
	cout<<dp[r]<<endl;
	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