Submission #1122949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122949		stefanneagu	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	818 ms	85644 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 2e5 + 1;

struct str {
	int a, i;
} v[nmax];

bool cmp(str x, str y) {
	return x.a < y.a;
}

vector<int> adj[nmax];
set<int> sz[nmax];
int root[nmax], d[nmax], dp[nmax], back[nmax], to[nmax];
int up[nmax][20];

int find(int a) {
	if(root[a] == a) {
		return a;
	}
	return root[a] = find(root[a]);
}

void unite(int a, int b) {
	if(a == b) {
		return;
	}
	if(sz[a].size() < sz[b].size()) {
		swap(a, b);
	}
	for(auto it : sz[b]) {
		sz[a].insert(it);
	}
	sz[b].clear();
	root[b] = a;
}

void dfs(int i, int tata = 0) {
	up[i][0] = tata;
	for(int j = 1; (1 << j) <= d[i]; j++) {
		up[i][j] = up[up[i][j - 1]][j - 1];
	}

	for(auto it : adj[i]) {
		if(it != tata) {
			d[it] = d[i] + 1;
			dfs(it, i);
		}
	}
}

int lift(int a, int nr) {
	for(int i = 0; (1 << i) <= nr; i++) {
		if((1 << i) & nr) {
			a = up[a][i];
		}
	}
	return a;
}

int get_dist(int a, int b) {
	if(d[a] > d[b]) {
		swap(a, b);
	}
	int l = 0, r = d[a], ans = 0;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(l == -1) {
			exit(0);
		}
		//while(true);
		if(lift(a, mid) == lift(b, mid + d[b] - d[a])) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return 2 * ans + d[b] - d[a];
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
		cin >> v[i].a;
		back[v[i].a] = i;
		v[i].i = i;
		root[i] = i;
	}
	sort(v + 1, v + n + 1, cmp);
	for(int i = 1; i <= n; i++) {
		to[v[i].i] = i;
	}
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1);
	for(int i = 1; i <= n; i++) {
		for(auto it : adj[v[i].i]) {
			if(v[to[it]].a < v[i].a) {
				if(sz[find(it)].size() != 0) {
					int x = back[*sz[find(it)].rbegin()];
					dp[v[i].i] = max(dp[v[i].i], dp[x] + get_dist(v[i].i, x));
					// cout << v[i].i << " " << x << " " << dp[v[i].i] << '\n';
				}
				unite(find(it), find(v[i].i));
			}
		}
		sz[find(v[i].i)].insert(v[i].a);
	}
	cout << dp[back[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