oj.uz

Submission #734192

# Submission time Handle Problem Language Result Execution time Memory
734192 2023-05-02T04:07:31 Z SanguineChameleon Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 5332 KB 
#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];

void dfs(int u, int p) {
	int tot = 0;
	vector<int> gain;
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != p) {
			par_w[v] = w;
			dfs(v, u);
			tot += max(dp[v][0], dp[v][1]);
			gain.push_back(w + dp[v][0] - max(dp[v][0], dp[v][1]));
		}
	}
	sort(gain.begin(), gain.end(), greater<int>());
	dp[u][0] = tot;
	dp[u][1] = max(tot, !gain.empty() ? tot + gain[0] + par_w[u] : -1);
}

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);
	}
	int res = 0;
	for (int u = 1; u <= n; u++) {
		dfs(u, -1);
		res = max(res, dp[u][0]);
	}
	cout << res;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 5024 KB Output is correct
17 Correct 6 ms 4948 KB Output is correct
18 Correct 5 ms 4948 KB Output is correct
19 Correct 5 ms 5020 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 5 ms 4948 KB Output is correct
22 Correct 4 ms 5024 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 5024 KB Output is correct
17 Correct 6 ms 4948 KB Output is correct
18 Correct 5 ms 4948 KB Output is correct
19 Correct 5 ms 5020 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 5 ms 4948 KB Output is correct
22 Correct 4 ms 5024 KB Output is correct
23 Execution timed out 1064 ms 5332 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 5024 KB Output is correct
17 Correct 6 ms 4948 KB Output is correct
18 Correct 5 ms 4948 KB Output is correct
19 Correct 5 ms 5020 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 5 ms 4948 KB Output is correct
22 Correct 4 ms 5024 KB Output is correct
23 Execution timed out 1064 ms 5332 KB Time limit exceeded
24 Halted 0 ms 0 KB -