oj.uz

Submission #931851

# Submission time Handle Problem Language Result Execution time Memory
931851 2024-02-22T12:31:00 Z Xiaoyang Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 252 ms 68212 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 1ll<<60
#define rep(i,a,b) for (ll i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
#define endl "\n"
void inc(ll &a,ll b) {a=(a+b)%mod;}
void dec(ll &a,ll b) {a=(a-b+mod)%mod;}
int prod(ll a,ll b) {return ll(a)*ll(b)%mod;}
int lowbit(ll x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const ll maxn=222222;
ll ht[maxn],dep[maxn],up[20][maxn],sz[maxn],fa[maxn];
ll dp[maxn];
vector<ll>alist[maxn];

//dp i is the max distance that cat moves at pillar with height i
void init(){
	rep(i,0,maxn)sz[i]=1,fa[i]=i;
}

ll findset(ll u){
	if(fa[u]==u)return u;
	return fa[u]=findset(fa[u]);
}

bool mergeset(ll u,ll v){
	u=findset(u);
	v=findset(v);
	if(u!=v){
		if(sz[u]<sz[v])swap(u,v);
		fa[v]=u;
		sz[u]+=sz[v];
	}
	
}

void dfs(ll u,ll p){
	up[0][u]=p;
	for(auto x:alist[u]){
		if(x==p)continue;
		dep[x]=dep[u]+1;
		dfs(x,u);
	}
}

ll lca(ll a,ll b){
	if(dep[a]<dep[b])swap(a,b);
	ll k=dep[a]-dep[b];
	rep(i,0,20){
		if((1ll<<i)&k)a=up[i][a];
	}
	if(a==b)return a;
	for(ll i=19;i>=0;i--){
		if(up[i][a]!=up[i][b]){
			a=up[i][a];
			b=up[i][b];
		}
	}
	return up[0][a];
}
ll dis(ll a,ll b){
	return dep[a]+dep[b]-2*dep[lca(a,b)];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("i.txt","r",stdin);
	ll n;cin>>n;
	rep(i,1,n+1)cin>>ht[i];
	rep(i,1,n){
		ll a,b;cin>>a>>b;
		alist[ht[a]].pb(ht[b]);
		alist[ht[b]].pb(ht[a]);
	}
	init();
	memset(up,-1,sizeof up);
	dfs(1,-1);
	rep(k,1,20){
		rep(i,1,n+1){
			if(up[k-1][i]!=-1){
				up[k][i]=up[k-1][up[k-1][i]];
			}
		}
	}
	rep(i,1,n+1){//iterate all the p values
		for(auto x:alist[i]){
			x=findset(x);
			if(x<i){
				fa[x]=i;
				dp[i]=max(dp[i],dp[x]+dis(i,x));
			}
		}
	}
	cout<<dp[n];
	return 0;
}

Compilation message

Main.cpp: In function 'bool mergeset(ll, ll)':
Main.cpp:50:1: warning: no return statement in function returning non-void [-Wreturn-type]
   50 | }
      | ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47704 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 10 ms 47764 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 7 ms 47704 KB Output is correct
10 Correct 8 ms 47708 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47704 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 10 ms 47764 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 7 ms 47704 KB Output is correct
10 Correct 8 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 7 ms 47704 KB Output is correct
13 Correct 8 ms 47704 KB Output is correct
14 Correct 7 ms 47708 KB Output is correct
15 Correct 7 ms 47712 KB Output is correct
16 Correct 7 ms 47732 KB Output is correct
17 Correct 7 ms 47712 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47704 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 10 ms 47764 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 7 ms 47704 KB Output is correct
10 Correct 8 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 7 ms 47704 KB Output is correct
13 Correct 8 ms 47704 KB Output is correct
14 Correct 7 ms 47708 KB Output is correct
15 Correct 7 ms 47712 KB Output is correct
16 Correct 7 ms 47732 KB Output is correct
17 Correct 7 ms 47712 KB Output is correct
18 Correct 9 ms 47968 KB Output is correct
19 Correct 9 ms 48220 KB Output is correct
20 Correct 9 ms 48220 KB Output is correct
21 Correct 10 ms 48088 KB Output is correct
22 Correct 10 ms 48224 KB Output is correct
23 Correct 10 ms 47968 KB Output is correct
24 Correct 10 ms 48064 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47704 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 10 ms 47764 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 7 ms 47704 KB Output is correct
10 Correct 8 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 7 ms 47704 KB Output is correct
13 Correct 8 ms 47704 KB Output is correct
14 Correct 7 ms 47708 KB Output is correct
15 Correct 7 ms 47712 KB Output is correct
16 Correct 7 ms 47732 KB Output is correct
17 Correct 7 ms 47712 KB Output is correct
18 Correct 9 ms 47968 KB Output is correct
19 Correct 9 ms 48220 KB Output is correct
20 Correct 9 ms 48220 KB Output is correct
21 Correct 10 ms 48088 KB Output is correct
22 Correct 10 ms 48224 KB Output is correct
23 Correct 10 ms 47968 KB Output is correct
24 Correct 10 ms 48064 KB Output is correct
25 Correct 9 ms 47712 KB Output is correct
26 Correct 9 ms 48032 KB Output is correct
27 Correct 10 ms 48220 KB Output is correct
28 Correct 9 ms 48020 KB Output is correct
29 Correct 9 ms 48224 KB Output is correct
30 Correct 10 ms 48096 KB Output is correct
31 Correct 10 ms 47964 KB Output is correct
32 Correct 10 ms 47964 KB Output is correct
33 Correct 10 ms 47964 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47704 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 10 ms 47764 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 7 ms 47704 KB Output is correct
10 Correct 8 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 7 ms 47704 KB Output is correct
13 Correct 8 ms 47704 KB Output is correct
14 Correct 7 ms 47708 KB Output is correct
15 Correct 7 ms 47712 KB Output is correct
16 Correct 7 ms 47732 KB Output is correct
17 Correct 7 ms 47712 KB Output is correct
18 Correct 9 ms 47968 KB Output is correct
19 Correct 9 ms 48220 KB Output is correct
20 Correct 9 ms 48220 KB Output is correct
21 Correct 10 ms 48088 KB Output is correct
22 Correct 10 ms 48224 KB Output is correct
23 Correct 10 ms 47968 KB Output is correct
24 Correct 10 ms 48064 KB Output is correct
25 Correct 81 ms 63704 KB Output is correct
26 Correct 88 ms 68212 KB Output is correct
27 Correct 86 ms 68180 KB Output is correct
28 Correct 120 ms 67668 KB Output is correct
29 Correct 131 ms 63800 KB Output is correct
30 Correct 115 ms 66640 KB Output is correct
31 Correct 114 ms 65872 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47836 KB Output is correct
2 Correct 7 ms 47708 KB Output is correct
3 Correct 224 ms 60652 KB Output is correct
4 Correct 211 ms 60240 KB Output is correct
5 Correct 217 ms 60240 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47704 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 10 ms 47764 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 8 ms 47708 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 7 ms 47704 KB Output is correct
10 Correct 8 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 7 ms 47704 KB Output is correct
13 Correct 8 ms 47704 KB Output is correct
14 Correct 7 ms 47708 KB Output is correct
15 Correct 7 ms 47712 KB Output is correct
16 Correct 7 ms 47732 KB Output is correct
17 Correct 7 ms 47712 KB Output is correct
18 Correct 9 ms 47968 KB Output is correct
19 Correct 9 ms 48220 KB Output is correct
20 Correct 9 ms 48220 KB Output is correct
21 Correct 10 ms 48088 KB Output is correct
22 Correct 10 ms 48224 KB Output is correct
23 Correct 10 ms 47968 KB Output is correct
24 Correct 10 ms 48064 KB Output is correct
25 Correct 9 ms 47712 KB Output is correct
26 Correct 9 ms 48032 KB Output is correct
27 Correct 10 ms 48220 KB Output is correct
28 Correct 9 ms 48020 KB Output is correct
29 Correct 9 ms 48224 KB Output is correct
30 Correct 10 ms 48096 KB Output is correct
31 Correct 10 ms 47964 KB Output is correct
32 Correct 10 ms 47964 KB Output is correct
33 Correct 10 ms 47964 KB Output is correct
34 Correct 81 ms 63704 KB Output is correct
35 Correct 88 ms 68212 KB Output is correct
36 Correct 86 ms 68180 KB Output is correct
37 Correct 120 ms 67668 KB Output is correct
38 Correct 131 ms 63800 KB Output is correct
39 Correct 115 ms 66640 KB Output is correct
40 Correct 114 ms 65872 KB Output is correct
41 Correct 9 ms 47836 KB Output is correct
42 Correct 7 ms 47708 KB Output is correct
43 Correct 224 ms 60652 KB Output is correct
44 Correct 211 ms 60240 KB Output is correct
45 Correct 217 ms 60240 KB Output is correct
46 Correct 107 ms 66164 KB Output is correct
47 Correct 110 ms 65960 KB Output is correct
48 Correct 109 ms 65872 KB Output is correct
49 Correct 110 ms 65832 KB Output is correct
50 Correct 239 ms 59812 KB Output is correct
51 Correct 232 ms 59988 KB Output is correct
52 Correct 237 ms 59964 KB Output is correct
53 Correct 252 ms 60236 KB Output is correct