oj.uz

Submission #567940

# Submission time Handle Problem Language Result Execution time Memory
567940 2022-05-24T11:31:57 Z flappybird Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 5052 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pii> adj[MAX];
ll X[MAX];
ll dp1[MAX];
ll dp2[MAX];
void dfs(int x, int p = 0) { for (auto& [v, c] : adj[x]) if (v != p) X[v] = c, dfs(v, x); }
void calc(int x, int p = 0) {
	ll mx, mx2;
	mx = mx2 = -INF;
	ll sum = 0;
	for (auto& [v, c] : adj[x]) if (v != p) {
		calc(v, x);
		sum += max(dp1[v], dp2[v]);
		ll dif = dp2[v] + X[v] - max(dp1[v], dp2[v]);
		if (mx2 < dif) mx2 = dif;
		if (mx2 > mx) swap(mx, mx2);
	}
	dp1[x] = max(0ll, X[x] + sum + mx);
	dp2[x] = max(0ll, sum + max(0ll, mx + mx2));
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	int a, b, c;
	for (i = 1; i < N; i++) {
		cin >> a >> b >> c;
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}
	dfs(1);
	calc(1);
	cout << dp2[1] << Ln;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4968 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 4 ms 5052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4968 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 4 ms 5052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4968 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 4 ms 5052 KB Output isn't correct
7 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 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4968 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 4 ms 5052 KB Output isn't correct
7 Halted 0 ms 0 KB -