Submission #888454

#	Time	Username	Problem	Language	Result	Execution time	Memory
888454		rorro	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	332 ms	54632 KiB

Main

#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define ll long long
#define lld long double
#define st first
#define nd second
#define mp make_pair
#define ii pair<int, int>
#define vll vector<ll>
#define vi vector<int>
#define vvi vector<vector<int> >
#define pb push_back
#define eb emplace_back
#define remax(a, b) a = max(a, b);
#define remin(a, b) a = min(a, b);
#define all(x) x.begin(), x.end()
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bit(n, x) (n & (1 << x))
#define rep(a, b) for(int a = 0; a < b; ++a)

using namespace std;

const int maxn = 2e5;
const int maxlog = 19;
vvi up(maxn, vi(maxlog));
vvi g(maxn);
vi par(maxn);
vi sz(maxn, 1);
vi depth(maxn);
vll ans(maxn, 0);
vi h(maxn);
vi mx(maxn); //vertex, h[mx[find_(v)]] to max h w spojnej z v

void dfs(int cur, int pare) {
	depth[cur] = depth[pare]+1;
	up[cur][0] = pare;
	for (int i = 1; i < maxlog; ++i) up[cur][i] = up[up[cur][i-1]][i-1];
	for (int u : g[cur]) {
		if (u != pare) {
			dfs(u, cur);
		}
	}
}

int dist(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v); //u jest glebiej niz v
	int dt = depth[u]-depth[v];
	for (int i = maxlog-1; i >= 0; --i) {
		if (depth[up[u][i]] >= depth[v]) u = up[u][i]; //{cout << "hi " << u << endl; u = up[u][i];}
	}
	//teraz sa tak samo gleboko
	if (u == v) return dt;
	//teraz sa rozne, i na tej samej glebokosci
	for (int i = maxlog-1; i >= 0; --i) {
		if (up[u][i] != up[v][i]) {
			u = up[u][i], v = up[v][i];
			dt += (1<<(1+i));
		}
	}
	return dt + 2;
}

int find_(int a) {
	if (a == par[a]) return a;
	return par[a] = find_(par[a]);
}

void join_(int a, int b) {
	a = find_(a), b = find_(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];
	//remax(mx[a], h[mx[b]]);
	if (h[mx[a]] < h[mx[b]]) mx[a] = mx[b];
	remax(ans[a], ans[b]);
	par[b] = a;
}

int main() {
	fastio();
	iota(all(par), 0), iota(all(mx), 0);
	int n;
	cin >> n;
	vector<ii> q(n);
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
		q[i] = mp(h[i], i);
	}
	sort(all(q));
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a;--b;
		g[a].eb(b);
		g[b].eb(a);
	}
	depth[0] = -1;
	dfs(0, 0);
	/*rep(i, n) {
		rep(j, n) {
			cout << "i: " << i << " j: " << j << " d[i]: " << depth[i] << " d[j]: " << depth[j] << endl;
			cout << "dist: " << dist(i, j) << endl;
		}
	}*/
	for (int i = 0; i < n; ++i) {
		const int cur = q[i].nd, curh = q[i].st;
		for (int u : g[cur]) {
			if (h[u] < curh) {
				u = find_(u);
				//remax(ans[u], ans[u]+dist(mx[u], cur));
				ans[u] += dist(mx[u], cur);
				join_(cur, u);
			}
		}
	}
	cout << ans[find_(0)] << '\n'; //+dist(n-1, q[n-1].nd) << '\n';


	return 0;
}

• 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