oj.uz

Submission #741844

# Submission time Handle Problem Language Result Execution time Memory
741844 2023-05-15T01:47:23 Z jamezzz Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 4 ms 5148 KB 
#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 v:AL[u]){
		if(v==p[0][u])continue;
		p[0][v]=u;
		d[v]=d[u]+1;
		dfs(v);
	}
	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]];
	}
}

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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5148 KB Output is correct
2 Incorrect 4 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Incorrect 3 ms 5132 KB Output isn't correct
3 Halted 0 ms 0 KB -