Submission #967347

# Submission time Handle Problem Language Result Execution time Memory
967347 2024-04-22T02:36:00 Z TranGiaHuy1508 Cat Exercise (JOI23_ho_t4) C++17
54 / 100
177 ms 43332 KB
#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";
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 3 ms 1372 KB Output is correct
20 Correct 4 ms 1372 KB Output is correct
21 Correct 2 ms 1372 KB Output is correct
22 Correct 3 ms 1372 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 3 ms 1372 KB Output is correct
20 Correct 4 ms 1372 KB Output is correct
21 Correct 2 ms 1372 KB Output is correct
22 Correct 3 ms 1372 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 3 ms 1372 KB Output is correct
27 Correct 3 ms 1372 KB Output is correct
28 Correct 3 ms 1372 KB Output is correct
29 Correct 3 ms 1232 KB Output is correct
30 Correct 3 ms 1116 KB Output is correct
31 Correct 3 ms 1116 KB Output is correct
32 Correct 3 ms 1124 KB Output is correct
33 Correct 3 ms 1112 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 3 ms 1372 KB Output is correct
20 Correct 4 ms 1372 KB Output is correct
21 Correct 2 ms 1372 KB Output is correct
22 Correct 3 ms 1372 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Incorrect 108 ms 43332 KB Output isn't correct
26 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 154 ms 33924 KB Output is correct
4 Correct 172 ms 33860 KB Output is correct
5 Correct 177 ms 33924 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 3 ms 1372 KB Output is correct
19 Correct 3 ms 1372 KB Output is correct
20 Correct 4 ms 1372 KB Output is correct
21 Correct 2 ms 1372 KB Output is correct
22 Correct 3 ms 1372 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 3 ms 1372 KB Output is correct
27 Correct 3 ms 1372 KB Output is correct
28 Correct 3 ms 1372 KB Output is correct
29 Correct 3 ms 1232 KB Output is correct
30 Correct 3 ms 1116 KB Output is correct
31 Correct 3 ms 1116 KB Output is correct
32 Correct 3 ms 1124 KB Output is correct
33 Correct 3 ms 1112 KB Output is correct
34 Incorrect 108 ms 43332 KB Output isn't correct
35 Halted 0 ms 0 KB -