Submission #1158740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158740		elotelo966	Cat Exercise (JOI23_ho_t4)	C++20	7 / 100	108 ms	164680 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define lim 20
#define mid (start+end)/2
#define pb push_back

int n,l;

int dizi[lim],dp[lim][(1<<lim)];

vector<int> v[lim];

int timer,tin[lim],tout[lim],dist[lim];

int up[lim][35],ger[lim][35];

inline void dfs(int node,int ata){
	tin[node]=tout[node]=++timer;
	dist[node]=dist[ata]+1;
	up[node][0]=ata;
	ger[node][0]=dizi[ata];
	for(int i=1;i<=l;i++){
		up[node][i]=up[up[node][i-1]][i-1];
		ger[node][i]=max(ger[node][i-1],ger[up[node][i-1]][i-1]);
	}
	for(auto go:v[node]){
		if(go==ata)continue;
		dfs(go,node);
		tout[node]=max(tout[node],tout[go]);
	}
}

inline bool anc(int node1,int node2){
	return tin[node1]<=tin[node2] && tout[node1]>=tout[node2];
}

inline int find_lca(int node1,int node2){
	if(anc(node1,node2))return node1;
	if(anc(node2,node1))return node2;
	for(int i=l;i>=0;i--){
		if(up[node1][i]!=0 && (!anc(up[node1][i],node2)))node1=up[node1][i];
	}
	return up[node1][0];
}

inline int con(int node1,int node2){
	if(node1==node2)return dizi[node1];
	int cev=dizi[node1];
	for(int i=l;i>=0;i--){
		if(up[node1][i]!=0 && (!anc(up[node1][i],node2))){
			cev=max(cev,ger[node1][i]);
			node1=up[node1][i];
		}
	}
	cev=max(cev,ger[node1][0]);
	return cev;
}

inline int f(int node,int mask){
	//cout<<node<<endl;
	if(~dp[node][mask])return dp[node][mask];
	int cev=0;
	FOR{
        if(mask&(1<<i))continue;
		int lca=find_lca(i,node);
		int distance=dist[i]+dist[node]-2*dist[lca];
		int maxi=0;
		maxi=max(maxi,con(i,lca));
		maxi=max(maxi,con(node,lca));
		//cout<<node<<" "<<i<<" "<<maxi<<" "<<dizi[node]<<" "<<distance<<endl;
		if(maxi<=dizi[node]){// check
			cev=max(cev,f(i,mask|(1<<i))+distance);
		}
	}
	return dp[node][mask]=cev;
}

int32_t main(){
	faster
	memset(dp,-1,sizeof(dp));
	cin>>n;
	l=ceil(log2(n));
	int baslangic;
	FOR{
		cin>>dizi[i];
		if(dizi[i]==n)baslangic=i;
	}
	
	FOR{
		if(i==1)continue;
		int x,y;cin>>x>>y;
		v[x].pb(y);
		v[y].pb(x);
	}
	
	dfs(1,0);
	
	cout<<f(baslangic,0)<<'\n';
	
	return 0;
}

• Subtask 1: 7 / 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