Submission #741860

#	Time	Username	Problem	Language	Result	Execution time	Memory
741860		jamezzz	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	573 ms	48088 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define INF 2023456789
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;

#define maxn 200005

int n,a[maxn],d[maxn],pos[maxn],par[maxn],rnk[maxn],mx[maxn],p[20][maxn];
ll dp[maxn];
vector<int> AL[maxn];

int fp(int i){return par[i]==i?i:par[i]=fp(par[i]);}
void join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return;
	if(rnk[x]<rnk[y])par[x]=y;
	else par[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
	mx[par[x]]=max(mx[x],mx[y]);
}

void dfs(int u){
	for(int k=1;k<20;++k){
		if(p[k-1][u]==-1)p[k][u]=-1;
		else p[k][u]=p[k-1][p[k-1][u]];
	}
	for(int v:AL[u]){
		if(v==p[0][u])continue;
		p[0][v]=u;
		d[v]=d[u]+1;
		dfs(v);
	}
}

int lca(int a,int b){
	if(d[a]<d[b])swap(a,b);
	for(int k=19;k>=0;--k){
		if(p[k][a]!=-1&&d[p[k][a]]>=d[b])a=p[k][a];
	}
	if(a==b)return a;
	for(int k=19;k>=0;--k){
		if(p[k][a]!=p[k][b])a=p[k][a],b=p[k][b];
	}
	return p[0][a];
}

inline int dist(int a,int b){
	return d[a]+d[b]-2*d[lca(a,b)];
}

int main(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		sf("%d",&a[i]);
		pos[a[i]]=i;
		par[i]=i,mx[i]=a[i];
	}
	for(int i=0;i<n-1;++i){
		int a,b;sf("%d%d",&a,&b);
		AL[a].pb(b);AL[b].pb(a);
	}
	p[0][1]=-1;
	dfs(1);
	for(int i=2;i<=n;++i){
		int u=pos[i];
		for(int v:AL[u]){
			if(a[v]>i)continue;
			int m=mx[fp(v)];
			int w=pos[m];
			dp[i]=max(dp[i],dp[m]+dist(u,w));
			join(u,v);
		}
	}
	pf("%lld\n",dp[n]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:60:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  sf("%d",&n);
      |    ^
Main.cpp:62:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   sf("%d",&a[i]);
      |     ^
Main.cpp:67:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   int a,b;sf("%d%d",&a,&b);
      |             ^

• 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