oj.uz

Submission #924984

# Submission time Handle Problem Language Result Execution time Memory
924984 2024-02-10T09:39:56 Z thinknoexit Beads and wires (APIO14_beads) C++17
0 / 100
 2 ms 10588 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
const ll INF = 2e9;
vector<pair<int, int>> adj[N];
ll dp[5][N];
void dfs(int v, int p = -1) {
    ll mx0 = 0, mx2 = -INF, mx3 = -INF;
    ll mx[3] = { -INF, -INF, -INF };
    for (auto& [x, w] : adj[v]) {
        if (x == p) continue;
        dfs(x, v);
        ll val = max(dp[1][x], dp[2][x] + w);
        // 0
        dp[0][v] += val;
        mx0 = max(mx0, max(dp[0][x], dp[3][x] + w) - val);
        // 1
        dp[1][v] += val;
        // 2
        dp[2][v] += val;
        mx2 = max(mx2, dp[1][x] + w - val);
        // 3
        dp[3][v] += val;
        mx3 = max(mx3, dp[4][x] + w - val);
        // 4
        dp[4][v] += val;
        mx[1] = max(mx[1], dp[1][x] + w - val);
        mx[2] = max(mx[2], dp[4][x] + w - val);
        if (mx[0] < mx[1]) swap(mx[0], mx[1]);
    }
    dp[0][v] += mx0;
    dp[2][v] += mx2;
    dp[3][v] += mx3;
    dp[4][v] += max(mx[0] + mx[1], mx[0] + mx[2]);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1;i < n;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    dfs(1);
    cout << max(dp[0][1], dp[4][1]);
    return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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