Submission #1263608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263608		kustov_vadim_533	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	337 ms	89628 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define len(v) (int)((v).size())

template<typename T>
ostream& operator<<(ostream& out, const vector<T> &a){
	for  (auto& x : a){
		out << x << ' ';
	}
	out << '\n';
	return out;
}

template<typename T>
istream& operator>>(istream& in, vector<T> &a){
	for (size_t i = 0; i < a.size(); ++i){
		in >> a[i];
	}
	return in;
}

#define int ll

mt19937 gen;

struct obj{
	ll vl = -1e18, add = 0;
	int i = -1;

	obj() = default;
	obj(int i, int x) : vl(x), i(i) {}
};

obj merge(obj &a, obj &b){
	if (a.vl > b.vl){
		return a;
	}
	else {
		return b;
	}
}

const int sz = 1 << 20;
obj tree[sz];

void push(int v, int ln){
	if (tree[v].add == 0) return;

	if (ln > 1){
		tree[v * 2].add += tree[v].add;
		tree[v * 2 + 1].add += tree[v].add;
	}

	tree[v].vl += tree[v].add;
	tree[v].add = 0;
}

void upd(int v, int l, int r, int ql, int qr, int qx){
	push(v, r - l);
	if (l >= qr || ql >= r) return;
	if (l >= ql && r <= qr) {
		tree[v].add += qx;
		push(v, r - l);
		return;
	}
	int m = (l + r) / 2;
	upd(v * 2, l, m, ql, qr, qx);
	upd(v * 2 + 1, m, r, ql, qr, qx);
	tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}

obj sum(int v, int l, int r, int ql, int qr){
	push(v, r - l);
	if (l >= qr || ql >= r) return obj();
	if (l >= ql && r <= qr) return tree[v];
	int m = (l + r) / 2;
	obj r1 = sum(v * 2, l, m, ql, qr);
	obj r2 = sum(v * 2 + 1, m, r, ql, qr);
	return merge(r1, r2);
}

void build(int v, int l, int r, vector<obj>& a){
	if (r - l == 1){
		tree[v] = a[l];
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m, a);
	build(v * 2 + 1, m, r, a);
	tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}

const int N = 2e5 + 7;
vector<int> g[N];
int a[N];
bool us[N];

int tim = 0;
int tin[N], tout[N], p[N], h[N];

void dfs2(int v, int pre){
	tin[v] = tim++;
	p[v] = pre;
	h[v] = h[pre] + 1;
	for (int u : g[v]){
		if (u == pre) continue;
		dfs2(u, v);
	}
	tout[v] = tim;
}


const int LGN = 20;
int up[LGN][N];

int la(int v, int k){
	for (int j = LGN - 1; j >= 0; --j){
		if (k >= (1 << j)){
			k -= (1 << j);
			v = up[j][v];
		}
	}
	return v;
}

int lca(int v, int u){
	v = la(v, h[v] - h[u]);
	u = la(u, h[u] - h[v]);
	if (v == u) return v;

	for (int j = LGN - 1; j >= 0; --j){
		if (up[j][v] != up[j][u]){
			v = up[j][v];
			u = up[j][u];
		}
	}
	return up[0][v];
}

int dist(int v, int u){
	return h[v] + h[u] - 2 * h[lca(u, v)];
}


int n;

const int inf = 1e9;

ll dfs(int v){
	obj r = sum(1, 0, n, 0, n);
	int ds = dist(v, r.i);
	v = r.i;

	ll res = 0;

	us[v] = true;
	for (int u : g[v]){
		if (us[u]) continue;
		if (u == p[v]){
			upd(1, 0, n, tin[v], tout[v], -inf);
			res = max(res, dfs(u));
			upd(1, 0, n, tin[v], tout[v], inf);
		}
		else{
			upd(1, 0, n, 0, n, -inf);
			upd(1, 0, n, tin[u], tout[u], inf);
			res = max(res, dfs(u));
			upd(1, 0, n, 0, n, inf);
			upd(1, 0, n, tin[u], tout[u], -inf);

		}
	}
//	us[v] = false;

	return res + ds + 1;
}


inline void solve() {
	cin >> n;

	for (int i = 0; i < n; ++i){
		cin >> a[i];
		us[i] = false;
	}

	for (int i = 0; i < n - 1; ++i){
		int x, y;
		cin >> x >> y;
		g[--x].push_back(--y);
		g[y].push_back(x);
	}

	dfs2(0, 0);

	for (int i = 0; i < n; ++i){
		up[0][i] = p[i];
	}

	for (int j = 1; j < LGN; ++j){
		for (int i = 0; i < n; ++i){
			up[j][i] = up[j - 1][up[j - 1][i]];
		}
	}

	vector<obj> init(n);
	for (int i = 0; i < n; ++i){
		init[tin[i]] = obj(i, a[i]);
	}

	build(1, 0, n, init);

	int ans = 0;
	for (int i = 0; i < n; ++i){
		if (a[i] == n){
			ans = dfs(i);
		}
	}
	cout << ans - 1 << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(60);

	int t = 1;
//	cin >> t;

	while (t--) {
		solve();
	}
}

• 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