Submission #1261504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261504		vlomaczk	Cat Exercise (JOI23_ho_t4)	C++20	0 / 100	19 ms	30280 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int M = 200'010;
int maxlog = 17;
vector<vector<pair<int, int>>> g(M);
vector<int> p(M), h(M), depth(M);
vector<vector<int>> jump(M, vector<int>(maxlog+1));
vector<int> rep(M, 0), sajz(M, 1), maks(M, 0);
vector<vector<pair<int, int>>> rep_changes, sajz_changes, maks_changes;
vector<bool> turned_on(M, 0);

void mw_dfs(int v, int p, int a) {
	rep_changes.back().push_back({v, rep[v]});
	rep[v] = a;
	for(auto[u, k] : g[v]) if(u!=p && turned_on[k]) mw_dfs(u, v, a);
}

void Union(int a, int b) {
	a = rep[a];
	b = rep[b];
	if(a==b) return;
	if(sajz[b] > sajz[a]) swap(a, b);
	rep_changes.push_back({});
	sajz_changes.push_back({{a, sajz[a]}, {b, sajz[b]}});
	maks_changes.push_back({{a, maks[a]}, {b, maks[b]}});
	mw_dfs(b, 0, a);
	sajz[a] += sajz[b];
	maks[a] = max(maks[a], maks[b]);
}

void rollback() {
	for(auto[a, b] : rep_changes.back()) rep[a] = b;
	for(auto[a, b] : sajz_changes.back()) sajz[a] = b;
	for(auto[a, b] : maks_changes.back()) maks[a] = b;
	rep_changes.pop_back();
	sajz_changes.pop_back();
	maks_changes.pop_back();
}

int find_max(int v, int p) {
	int ans = v;
	for(auto[u, k] : g[v]) {
		if(u==p) continue;
		int fm = find_max(u, v);
		if(h[fm] > h[ans]) ans = fm;
	}
	return ans;
}

void jump_dfs(int v, int p) {
	depth[v] = depth[p] + 1;
	jump[v][0] = p;
	for(int i=1; i<=maxlog; ++i) jump[v][i] = jump[jump[v][i-1]][i-1];
	for(auto[u, k] : g[v]) if(u!=p) jump_dfs(u, v);
}

int lca(int a, int b) {
	if(depth[b] > depth[a]) swap(a, b);
	for(int i=maxlog; i>=0; --i) {
		if(depth[jump[a][i]] >= depth[b]) a = jump[a][i];
	}
	if(a==b) return a;
	for(int i=maxlog; i>=0; --i) {
		if(jump[a][i]!=jump[b][i]) {
			a = jump[a][i];
			b = jump[b][i];
		}
	}
	return jump[a][0];
}

int dist(int a, int b) {
	return depth[a] + depth[b] - 2*depth[lca(a, b)];
}

int ans(int v) {
	int odp = 0;
	for(auto[u, k] : g[v]) {
		if(turned_on[k]) rollback();
	}
	for(auto[u, k] : g[v]) {
		if(turned_on[k]) {
			turned_on[k] = 0;
			int fm = p[maks[rep[u]]];
			odp = max(odp, dist(v, fm)+ans(fm));
		}
	}
	return odp;
}

bool h_comp(int a, int b) {
	return h[a] < h[b];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for(int i=1; i<=n; ++i) {
		cin >> h[i];
		p[h[i]] = i;
	}
	for(int i=1; i<n; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	vector<int> vert;
	for(int i=1; i<=n; ++i) vert.push_back(i);
	for(int i=1; i<=n; ++i) rep[i] = i;
	for(int i=1; i<=n; ++i) maks[i] = h[i];
	sort(vert.begin(), vert.end(), h_comp);
	for(auto v : vert) {
		for(auto[u, k] : g[v]) {
			if(h[u] > h[v]) continue;
			Union(v, u);
			turned_on[k] = 1;
		}
	}
	jump_dfs(1, 0);
	cout << ans(p[n]) << "\n";

	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26