oj.uz

Submission #567931

# Submission time Handle Problem Language Result Execution time Memory
567931 2022-05-24T11:11:52 Z flappybird Beads and wires (APIO14_beads) C++17
0 / 100
 3 ms 5060 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 += dp1[v];
		ll dif = dp2[v] + X[v] - dp1[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 + 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 4996 KB Output is correct
3 Incorrect 3 ms 5060 KB Output isn't correct
4 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 4996 KB Output is correct
3 Incorrect 3 ms 5060 KB Output isn't correct
4 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 4996 KB Output is correct
3 Incorrect 3 ms 5060 KB Output isn't correct
4 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 4996 KB Output is correct
3 Incorrect 3 ms 5060 KB Output isn't correct
4 Halted 0 ms 0 KB -