Submission #1181981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181981		PieArmy	Cat Exercise (JOI23_ho_t4)	C++20	0 / 100	2 ms	5188 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];
int tim=0;
int spar[400023][18],lg[400023];
int from[200023];
ll dp[200023];
vector<int>v;

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;
	}
}

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]);
}

bool on_path(int a,int b,int c){
	int ab=lca(a,b),bc=lca(b,c),ac=lca(a,c);
	if(dep[c]<dep[ab])return false;
	if(bc==c||ac==c)return true;
	return false;
}

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

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

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<18;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(n);
	ll ans=0;
	cal();
	for(int i=n-1;i>=1;i--){
		if(int(v.size())*int(v.size())>=n){
			cal();
		}
		for(int j=0;j<v.size();j++){
			if(!on_path(loc[i],loc[v[j]],from[loc[i]])){
				from[loc[i]]=loc[v[j]];
			}
		}
		dp[loc[i]]=dp[from[loc[i]]]+dis(loc[i],from[loc[i]]);
		v.pb(i);
		ans=max(ans,dp[loc[i]]);
	}
	cout<<ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26