Submission #967347

#	Time	Username	Problem	Language	Result	Execution time	Memory
967347		TranGiaHuy1508	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	177 ms	43332 KiB

Main

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

const int lg = 18;

struct DSU {
	vector<int> parent;

	DSU() {}
	DSU(int N): parent(N, -1) {}

	int get(int x){
		return (parent[x] < 0) ? x : (parent[x] = get(parent[x]));
	}

	bool merge(int a, int b){
		a = get(a); b = get(b);
		if (a == b) return false;

		if (parent[a] > parent[b]) swap(a, b);
		parent[a] += parent[b];
		parent[b] = a;
		return true;
	}
};


int n;
vector<int> p;
vector<vector<int>> adj;

vector<int> best, dp;
vector<vector<int>> par;
vector<int> depth;

void dfs(int x, int P, int d = 0){
	par[0][x] = P;
	depth[x] = d;

	for (auto k: adj[x]){
		if (k == P) continue;
		dfs(k, x, d+1);
	}
}

void build(){
	par.resize(lg, vector<int>(n));
	depth.resize(n);
	dfs(0, 0);

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

int dist(int x, int y){
	int sum = 0;
	if (depth[x] > depth[y]) swap(x, y);
	for (int j = 0; j < lg; j++){
		if (((depth[y] - depth[x]) >> j) & 1){
			sum += (1 << j);
			y = par[j][y];
		}
	}
	if (x == y) return sum;

	for (int j = lg-1; j >= 0; j--){
		if (par[j][x] != par[j][y]){
			sum += (1 << (j + 1));
			x = par[j][x];
			y = par[j][y];
		}
	}

	return sum + 2;
}

void main_program(){
	cin >> n;

	p.resize(n);
	adj.resize(n);

	for (int i = 0; i < n; i++) cin >> p[i];

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

	build();

	vector<int> order(n);
	iota(order.begin(), order.end(), 0);
	sort(order.begin(), order.end(), [&](int x, int y){
		return p[x] < p[y];
	});

	best.resize(n);
	iota(best.begin(), best.end(), 0);
	dp.resize(n);

	DSU dsu(n);

	for (auto x: order){
		for (auto y: adj[x]){
			if (p[x] < p[y]) continue;

			int old_root = dsu.get(y);
			int old_best = best[old_root];

			dp[x] = max(dp[x], dp[old_best] + dist(old_best, x));

			dsu.merge(x, y);
			int root = dsu.get(x);

			best[root] = x;
		}
	}

	cout << dp[order.back()] << "\n";
}

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