Submission #1059373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059373		beaconmc	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	376 ms	101200 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
const ll maxn = 200005;

ll vals[maxn];
ll which[maxn+2];

bool visited[maxn];
vector<ll> edges[maxn];
vector<vector<ll>> edges2[maxn];


ll cmp[maxn];
ll maxis[maxn];



ll ancc[maxn][30];
ll depth[maxn];
ll par[maxn];

ll anc(ll a, ll x){
	if (a==0) return 0;
	if (x==0) return par[a];
	if (ancc[a][x] != -1) return ancc[a][x];

	return ancc[a][x] = anc(anc(a,x-1),x-1);
}

ll lca(ll a, ll b){
	if (depth[a] < depth[b]) swap(a,b);
	FORNEG(i,29,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);
	if (a==b) return a;
	FORNEG(i,29,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
	return par[a];
}


void initdfs(ll a, ll p, ll d){
	depth[a] = d;
	par[a] = p;
	for (auto&i : edges[a]) if (i != p) initdfs(i, a, d+1);
}

ll find(ll a){
	while (a != cmp[a]){
		cmp[a] = cmp[cmp[a]];
		a = cmp[a];
	}
	return a;
}
void unite(ll a, ll b){
	ll A = find(a);
	ll B = find(b);

	maxis[B] = max(maxis[B], maxis[A]);
	cmp[A] = B;
}



ll dp(ll a, ll p){
	ll ans = 0;
	for (auto&i : edges2[a]){
		if (i[0] != p) ans = max(ans, dp(i[0], a) + i[1]);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	FOR(i,0,maxn) cmp[i] = i, maxis[i] = -1;
	FOR(i,0,maxn) FOR(j,0,30) ancc[i][j] = -1;

	FOR(i,0,n){
		cin >> vals[i];
		which[vals[i]] = i;
		maxis[find(i)] = vals[i];
	}
	FOR(i,0,n-1){
		ll a,b;
		cin >> a >> b;
		a--;b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	initdfs(0,-1,0);



	FOR(i,1,n+1){
		ll root = which[i];

		for (auto&i : edges[root]){
			if (vals[i] > vals[root]) continue;
			ll maxi = which[maxis[find(i)]];

			edges2[root].push_back({maxi, depth[root]+depth[maxi] - 2*depth[lca(root, maxi)]});
			unite(root, i);
		}
	}


	ll root = which[n];
	cout << dp(root, -1);



}

• 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