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

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.0 / 7.0

#	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

Subtask #2
7.0 / 7.0

#	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

Subtask #3
7.0 / 7.0

#	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

Subtask #4
10.0 / 10.0

#	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

Subtask #5
0 / 20.0

#	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	-

Subtask #6
23.0 / 23.0

#	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

Subtask #7
0 / 26.0

#	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	-

Submission #967347

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 20.0

Subtask #6 23.0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
0 / 26.0