Submission #734198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
734198	2023-05-02T04:21:27 Z	SanguineChameleon	Beads and wires (APIO14_beads)	C++17	100 / 100	354 ms	43920 KB

beads

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxN = 2e5 + 20;
vector<pair<int, int>> adj[maxN];
int par_w[maxN];
int dp[maxN][2];
int tot[maxN];
multiset<int> gain[maxN];
int res;

void dfs1(int u, int p) {
	tot[u] = 0;
	gain[u].clear();
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != p) {
			par_w[v] = w;
			dfs1(v, u);
			tot[u] += max(dp[v][0], dp[v][1]);
			gain[u].insert(w + dp[v][0] - max(dp[v][0], dp[v][1]));
		}
	}
	dp[u][0] = tot[u];
	dp[u][1] = tot[u] + (!gain[u].empty() ? *gain[u].rbegin() + par_w[u] : 0);
}

void dfs2(int u, int p) {
	res = max(res, dp[u][0]);
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != p) {
			par_w[u] = w;
			par_w[v] = 0;

			tot[u] -= max(dp[v][0], dp[v][1]);
			gain[u].erase(gain[u].find(w + dp[v][0] - max(dp[v][0], dp[v][1])));

			dp[u][0] = tot[u];
			dp[u][1] = tot[u] + (!gain[u].empty() ? *gain[u].rbegin() + par_w[u] : 0);

			tot[v] += max(dp[u][0], dp[u][1]);
			gain[v].insert(w + dp[u][0] - max(dp[u][0], dp[u][1]));

			dp[v][0] = tot[v];
			dp[v][1] = tot[v] + (!gain[v].empty() ? *gain[v].rbegin() + par_w[v] : 0);

			dfs2(v, u);

			par_w[u] = 0;
			par_w[v] = w;

			gain[v].erase(gain[v].find(w + dp[u][0] - max(dp[u][0], dp[u][1])));
			tot[v] -= max(dp[u][0], dp[u][1]);

			dp[v][0] = tot[v];
			dp[v][1] = tot[v] + (!gain[v].empty() ? *gain[v].rbegin() + par_w[v] : 0);

			tot[u] += max(dp[v][0], dp[v][1]);
			gain[u].insert(w + dp[v][0] - max(dp[v][0], dp[v][1]));

			dp[u][0] = tot[u];
			dp[u][1] = tot[u] + (!gain[u].empty() ? *gain[u].rbegin() + par_w[u] : 0);
		}
	}
}

void just_do_it() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	dfs1(1, -1);
	dfs2(1, -1);
	cout << res;
}

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14432 KB	Output is correct
2	Correct	10 ms	14348 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14420 KB	Output is correct
5	Correct	7 ms	14404 KB	Output is correct
6	Correct	7 ms	14420 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	8 ms	14312 KB	Output is correct
9	Correct	8 ms	14380 KB	Output is correct
10	Correct	9 ms	14420 KB	Output is correct
11	Correct	9 ms	14420 KB	Output is correct
12	Correct	7 ms	14428 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14432 KB	Output is correct
2	Correct	10 ms	14348 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14420 KB	Output is correct
5	Correct	7 ms	14404 KB	Output is correct
6	Correct	7 ms	14420 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	8 ms	14312 KB	Output is correct
9	Correct	8 ms	14380 KB	Output is correct
10	Correct	9 ms	14420 KB	Output is correct
11	Correct	9 ms	14420 KB	Output is correct
12	Correct	7 ms	14428 KB	Output is correct
13	Correct	7 ms	14328 KB	Output is correct
14	Correct	7 ms	14420 KB	Output is correct
15	Correct	7 ms	14420 KB	Output is correct
16	Correct	9 ms	14424 KB	Output is correct
17	Correct	8 ms	14420 KB	Output is correct
18	Correct	7 ms	14420 KB	Output is correct
19	Correct	7 ms	14420 KB	Output is correct
20	Correct	8 ms	14384 KB	Output is correct
21	Correct	7 ms	14420 KB	Output is correct
22	Correct	7 ms	14420 KB	Output is correct

Subtask #3
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14432 KB	Output is correct
2	Correct	10 ms	14348 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14420 KB	Output is correct
5	Correct	7 ms	14404 KB	Output is correct
6	Correct	7 ms	14420 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	8 ms	14312 KB	Output is correct
9	Correct	8 ms	14380 KB	Output is correct
10	Correct	9 ms	14420 KB	Output is correct
11	Correct	9 ms	14420 KB	Output is correct
12	Correct	7 ms	14428 KB	Output is correct
13	Correct	7 ms	14328 KB	Output is correct
14	Correct	7 ms	14420 KB	Output is correct
15	Correct	7 ms	14420 KB	Output is correct
16	Correct	9 ms	14424 KB	Output is correct
17	Correct	8 ms	14420 KB	Output is correct
18	Correct	7 ms	14420 KB	Output is correct
19	Correct	7 ms	14420 KB	Output is correct
20	Correct	8 ms	14384 KB	Output is correct
21	Correct	7 ms	14420 KB	Output is correct
22	Correct	7 ms	14420 KB	Output is correct
23	Correct	10 ms	14892 KB	Output is correct
24	Correct	11 ms	14932 KB	Output is correct
25	Correct	11 ms	14932 KB	Output is correct
26	Correct	18 ms	15308 KB	Output is correct
27	Correct	13 ms	15572 KB	Output is correct
28	Correct	16 ms	15520 KB	Output is correct
29	Correct	15 ms	15572 KB	Output is correct
30	Correct	16 ms	15588 KB	Output is correct
31	Correct	18 ms	16096 KB	Output is correct

Subtask #4
43.0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14432 KB	Output is correct
2	Correct	10 ms	14348 KB	Output is correct
3	Correct	7 ms	14420 KB	Output is correct
4	Correct	7 ms	14420 KB	Output is correct
5	Correct	7 ms	14404 KB	Output is correct
6	Correct	7 ms	14420 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	8 ms	14312 KB	Output is correct
9	Correct	8 ms	14380 KB	Output is correct
10	Correct	9 ms	14420 KB	Output is correct
11	Correct	9 ms	14420 KB	Output is correct
12	Correct	7 ms	14428 KB	Output is correct
13	Correct	7 ms	14328 KB	Output is correct
14	Correct	7 ms	14420 KB	Output is correct
15	Correct	7 ms	14420 KB	Output is correct
16	Correct	9 ms	14424 KB	Output is correct
17	Correct	8 ms	14420 KB	Output is correct
18	Correct	7 ms	14420 KB	Output is correct
19	Correct	7 ms	14420 KB	Output is correct
20	Correct	8 ms	14384 KB	Output is correct
21	Correct	7 ms	14420 KB	Output is correct
22	Correct	7 ms	14420 KB	Output is correct
23	Correct	10 ms	14892 KB	Output is correct
24	Correct	11 ms	14932 KB	Output is correct
25	Correct	11 ms	14932 KB	Output is correct
26	Correct	18 ms	15308 KB	Output is correct
27	Correct	13 ms	15572 KB	Output is correct
28	Correct	16 ms	15520 KB	Output is correct
29	Correct	15 ms	15572 KB	Output is correct
30	Correct	16 ms	15588 KB	Output is correct
31	Correct	18 ms	16096 KB	Output is correct
32	Correct	49 ms	20184 KB	Output is correct
33	Correct	63 ms	20172 KB	Output is correct
34	Correct	66 ms	20072 KB	Output is correct
35	Correct	296 ms	37856 KB	Output is correct
36	Correct	303 ms	37944 KB	Output is correct
37	Correct	300 ms	37856 KB	Output is correct
38	Correct	354 ms	38276 KB	Output is correct
39	Correct	329 ms	38316 KB	Output is correct
40	Correct	328 ms	38148 KB	Output is correct
41	Correct	333 ms	43920 KB	Output is correct

Submission #734198

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 15.0 / 15.0

Subtask #3 29.0 / 29.0

Subtask #4 43.0 / 43.0

Subtask #1
13.0 / 13.0

Subtask #2
15.0 / 15.0

Subtask #3
29.0 / 29.0

Subtask #4
43.0 / 43.0