Submission #1182068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182068		PieArmy	Cat Exercise (JOI23_ho_t4)	C++20	31 / 100	2097 ms	61856 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];
vector<int>v;
int bigger[200023];

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=val[v[0]];
	for(int x:v){
		m=min(val[x],m);
	}
	v.clear();
	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);
}

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.pb(loc[n]);
	ll ans=0;
	cal();
	for(int i=n-1;i>=1;i--){
		if(int(v.size())*int(v.size())>=n){
			cal();
		}

		sort(v.begin(),v.end(),[&](const int &x,const int &y){
			return eu[x]<eu[y];
		});
		int par=-1;
		for(int j=0;j<v.size();j++){
			if(eu[loc[i]]>eu[v[j]]&&eu[loc[i]]<=son[v[j]]){
				par=j;
			}
		}
		if(par!=-1&&bigger[loc[i]]==bigger[v[par]]){
			from[loc[i]]=v[par];
		}
		int las=0;
		for(int j=par+1;j<v.size();j++){
			if(par!=-1&&eu[v[j]]>son[v[par]])break;
			if(las&&eu[v[j]]<=son[las])continue;
			las=v[j];
			if(bigger[loc[i]]+bigger[v[j]]==2*bigger[lca(loc[i],v[j])]){
				if(val[v[j]]<val[from[loc[i]]])from[loc[i]]=v[j];
			}
		}

		v.pb(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