Submission #911384

#	Time	Username	Problem	Language	Result	Execution time	Memory
911384		OAleksa	Cat Exercise (JOI23_ho_t4)	C++14	0 / 100	3 ms	15360 KiB

Main

#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 18;
int up[N][K], tin[N], tout[N], timer, dep[N];
int st[4 * N], act[4 * N];
int n, a[N], vis[N], bst[N];
vector<int> g[N];
void modify(int v, int tl, int tr, int p, int x) {
	if (tl == tr) {
		st[v] = x;
	}
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			modify(v * 2, tl, mid, p, x);
		else
			modify(v * 2 + 1, mid + 1, tr, p, x);
		if (a[st[v * 2]] > a[st[v * 2 + 1]])
			st[v] = st[v * 2];
		else
			st[v] = st[v * 2 + 1];
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l || act[v])
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		int left = get(v * 2, tl, mid, l, r);
		int right = get(v * 2 + 1, mid + 1, tr, l, r);
		if (a[left] > a[right])
			return left;
		return right;
	}
}
bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
void dfs(int v, int p) {
	up[v][0] = p;
	tin[v] = ++timer;
	dep[v] = dep[p] + 1;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	bst[v] = v;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
		if (a[bst[u]] > a[bst[v]]) 
			bst[v] = bst[u];
	}
	tout[v] = timer;
}
int Lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
int distance(int a, int b) {
	if (a == 0 || b == 0)
		return 0;
	int lc = Lca(a, b);
	return dep[a] + dep[b] - 2 * dep[lc];
}
pair<int, int> find_mx(int v, int p) {
	if (vis[v]) 
		return {0, 0};
	int mx = a[v], s = v;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		auto x = find_mx(u, v);
		if (x.f > mx) {
			mx = x.f;
			s = x.s;
		}
	}
	return {mx, s};
}
void activate(int v, int tl, int tr, int l, int r, int x) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r)
		act[v] = x;
	else {
		int mid = (tl + tr) / 2;
		activate(v * 2, tl, mid, l, r, x);
		activate(v * 2 + 1, mid + 1, tr, l, r, x);
		if (act[v * 2] == 1 && act[v * 2 + 1] == 1)
			st[v] = 0;
		else if (act[v * 2] == 1 && act[v * 2 + 1] == 0)
			st[v] = st[v * 2 + 1];
		else if (act[v * 2] == 0 && act[v * 2 + 1] == 1) {
			st[v] = st[v * 2];
		}
		else {
			if (a[st[v * 2]] > a[st[v * 2 + 1]])
				st[v] = st[v * 2];
			else
				st[v] = st[v * 2 + 1];
		}
	}
}
int solve(int x, int p) {
	int v = get(1, 1, n, tin[x], tout[x]);
	vis[v] = 1;
	int res = 0;
	for (auto u : g[v]) {
		if (vis[u])
			continue;
		if (dep[u] > dep[v]) 
			res = max(res, solve(u, v));	
		else {
			activate(1, 1, n, tin[v], tout[v], 1);
			res = max(res, solve(x, v));
			activate(1, 1, n, tin[v], tout[v], 0);
		}
	}
	return res + distance(v, p);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
  	for (int i = 1;i <= n;i++)	
  		cin >> a[i];
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		g[a].push_back(b);
  		g[b].push_back(a);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= n;i++)
  		modify(1, 1, n, tin[i], i);
  	cout << solve(1, 0) << '\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