Submission #1182223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182223		PieArmy	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	228 ms	72432 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

int n;
int val[200023],loc[200023];
int par[200023],siz[200023];
int from[200023];
ll dp[200023];
vector<int>komsu[200023];
set<int>st[200023];

int dep[200023];
int bin[200023][18];

int get(int x){
	if(x==par[x])return x;
	return par[x]=get(par[x]);
}

void unite(int a,int b){
	int A=get(a),B=get(b);
	if(siz[A]<siz[B]){
		swap(A,B);
		swap(a,b);
	}
	par[B]=A;
	siz[A]+=siz[B];
	st[A].erase(val[b]);
	st[B].erase(val[a]);
	if(st[B].size()>st[A].size()){
		swap(st[A],st[B]);
	}
	for(int x:st[B]){
		st[A].insert(x);
	}
	st[B].clear();
}

void dfs(int pos){
	for(int i=1;i<18;i++){
		bin[pos][i]=bin[bin[pos][i-1]][i-1];
	}
	for(int x:komsu[pos]){
		if(x==bin[pos][0])continue;
		bin[x][0]=pos;
		dep[x]=dep[pos]+1;
		dfs(x);
	}
}

int lca(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	for(int i=0;i<18;i++){
		if((1<<i)&(dep[a]-dep[b])){
			a=bin[a][i];
		}
	}
	if(a==b)return a;
	for(int i=18-1;i>=0;i--){
		if(bin[a][i]!=bin[b][i]){
			a=bin[a][i];
			b=bin[b][i];
		}
	}
	return bin[a][0];
}

int dis(int a,int b){
	return dep[a]+dep[b]-2*dep[lca(a,b)];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		siz[i]=1;
		par[i]=i;
		cin>>val[i];
		loc[val[i]]=i;
	}
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
		st[x].insert(val[y]);
		st[y].insert(val[x]);
	}
	dfs(1);
	ll ans=0;
	for(int i=1;i<n;i++){
		for(int x:komsu[loc[i]]){
			if(val[x]>i)continue;
			unite(loc[i],x);
		}
		from[loc[i]]=loc[*st[get(loc[i])].begin()];
	}
	for(int i=n-1;i>=1;i--){
		dp[loc[i]]=dp[from[loc[i]]]+dis(loc[i],from[loc[i]]);
		ans=max(ans,dp[loc[i]]);
	}
	cout<<ans;
}

• 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