Submission #1147013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147013		nuutsnoynton	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	321 ms	61256 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 2;
ll a[N], ind[N], val[N],used[N],  mx[N], d[N], mn[N], in[N], out[N], timer  = 0, P[20][N], dp[N];
vector < ll > adj[N];

bool is_ancestor(ll x, ll y) {
	if ( in[x] <= in[y] && out[y] <= out[x]) return true;
	return false;
}
ll lca(ll x, ll y) {
	if ( is_ancestor(x, y)) return x;
	if ( is_ancestor(y, x)) return y;
	for (int i = 18; i >= 0; i --) {
		if (!is_ancestor(P[i][x], y)) x= P[i][x];
	}
	x = P[0][x];
	return x;
}
ll path(ll x, ll y) {
	ll r = lca(x, y);
	r = d[x] + d[y] - 2 * d[r];
	return r;
}
void Go(ll x, ll p) {
	P[0][x] = p;
	for (int i = 1; i <= 18; i++) P[i][x] = P[i - 1][P[i- 1][x]];
	in[x] = ++timer;
	for (ll X : adj[x]) {
		if (X == p) continue;
		d[X] = d[x] + 1;
		Go(X, x);
	}
	out[x] = timer;
}

ll Mx(ll x, ll p) {
	ll s = x;
	for ( ll X : adj[x]) {
		if (used[X] == 1 || X == p) continue;
		s = max(s, Mx(X, x));
	}
	return s;
}
ll ataman[N];

ll Get(ll x) {
	if (x == ataman[x]) return x;
	return ataman[x]= Get(ataman[x]);
}

void Unite(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return ;
	if ( x > y) swap(x, y);
	ataman[x] = y;
}
void Solve(ll x) {
	for ( ll X : adj[x]) {
		if ( used[X] == 0) continue;
		ll x1 = Get(x);
		ll X1 = Get(X);
		if (x1 != X1) {
			dp[x1] = max(dp[x1], path(x1, X1) + dp[X1]);
			Unite(x1, X1);
		}
	}
	return ;
}

int main() {
	ll n, m, r, x, y, i, j, ans, t;
	
	cin >>n;
	
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (i = 1; i < n; i ++) {
		cin >> x >> y;
		adj[a[x]].push_back(a[y]);
		adj[a[y]].push_back(a[x]);
	}
	d[1] = 0;
	Go(n, n);
//	for (i = 1; i <= n; i ++) {
//		cout << d[i] << " ";
//	}
//	cout << "HI" << endl;
	for (i = 1; i <= n; i++) dp[i]=0 , ataman[i] = i;
	for (i = 1; i <= n; i ++) {
		used[i] = 1;
		Solve(i);
	}
	cout << dp[n] << endl;
	
	
}

• 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