Submission #1182089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182089		PieArmy	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	2096 ms	62424 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];
vector<int>komsu[200023];
int dep[200023],eu[200023],son[200023];
int tim=0;
int spar[400023][19],lg[400023];
int from[200023];
ll dp[200023];
int v[200023];
int bigger[200023];
int siz=0;

void dfs(int pos){
	spar[++tim][0]=pos;
	eu[pos]=tim;
	for(int x:komsu[pos]){
		if(eu[x])continue;
		dep[x]=dep[pos]+1;
		dfs(x);
		spar[++tim][0]=pos;
	}
	son[pos]=tim;
}

int query(int l,int r){
	int a=spar[l][lg[r-l+1]],b=spar[r-(1<<lg[r-l+1])+1][lg[r-l+1]];
	if(dep[a]<dep[b])return a;
	return b;
}

int lca(int a,int b){
	if(eu[a]>eu[b])swap(a,b);
	return query(eu[a],eu[b]);
}

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

void dfs2(int pos,int m){
	for(int x:komsu[pos]){
		if(dep[x]<dep[pos])continue;
		bigger[x]=bigger[pos];
		bigger[x]+=(val[pos]>=m);
		dfs2(x,m);
	}
}

void cal(){
	int m=n+1;
	{
		int x=v[0];
		while(x!=n+1){
			m=min(val[x],m);
			x=v[x];
		}
	}
	siz=0;
	v[0]=n+1;
	queue<int>q;
	for(int i=1;i<m;i++){
		from[loc[i]]=0;
		bigger[i]=0;
	}
	for(int i=m;i<=n;i++){
		q.push(loc[i]);
		while(q.size()){
			int pos=q.front();
			q.pop();
			if(loc[i]!=pos)from[pos]=loc[i];
			for(int x:komsu[pos]){
				if(val[x]>=i)continue;
				if(from[x])continue;
				q.push(x);
			}
		}
	}
	dfs2(1,m);
}

void ekle(int x){
	siz++;
	if(v[0]==n+1||eu[v[0]]>eu[x]){
		v[x]=v[0];
		v[0]=x;
		return;
	}
	for(int p=v[0];p!=n+1;p=v[p]){
		if(eu[p]<eu[x]&&(v[p]==n+1||eu[v[p]]>eu[x])){
			v[x]=v[p];
			v[p]=x;
			return;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	for(int i=2;i<=n*2;i++){
		lg[i]=lg[i/2]+1;
	}
	for(int i=1;i<=n;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);
	}
	dfs(1);
	for(int i=1;i<19;i++){
		for(int j=1;j+(1<<i)-1<=tim;j++){
			spar[j][i]=spar[j][i-1];
			int x=spar[j+(1<<(i-1))][i-1];
			if(dep[x]<dep[spar[j][i]])spar[j][i]=x;
		}
	}
	v[0]=n+1;
	ekle(loc[n]);
	ll ans=0;
	cal();
	for(int i=n-1;i>=1;i--){
		if(siz*siz>=n){
			cal();
		}

		int par=-1;
		for(int j=0,p=v[0];p!=n+1;j++,p=v[p]){
			if(eu[loc[i]]>eu[p]&&eu[loc[i]]<=son[p]){
				par=p;
			}
		}
		if(par!=-1&&bigger[loc[i]]==bigger[par]){
			from[loc[i]]=par;
		}
		int las=(!(par+1))-1;
		for(int j=0,p=v[0];p!=n+1;j++,p=v[p]){
			if(p==par){
				las=0;
				continue;
			}
			if(las==-1)continue;
			if(par!=-1&&eu[p]>son[par])break;
			if(las&&eu[p]<=son[las])continue;
			las=p;
			if(bigger[loc[i]]+bigger[p]==2*bigger[lca(loc[i],p)]){
				if(val[p]<val[from[loc[i]]])from[loc[i]]=p;
			}
		}

		ekle(loc[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: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26