oj.uz

Submission #757102

# Submission time Handle Problem Language Result Execution time Memory
757102 2023-06-12T15:57:57 Z thimote75 Beads and wires (APIO14_beads) C++14
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
using t_road  = pair<int, int>;
using t_roads = vector<t_road>;
using t_graph = vector<t_roads>;

using ipair = t_road;

int N;
t_graph tree;

void update (ipair &fmx_and_smx, int value) {
    if (fmx_and_smx.first <= value) {
        fmx_and_smx.second = fmx_and_smx.first;
        fmx_and_smx.first  = value;
    } else if (fmx_and_smx.second <= value)
        fmx_and_smx.second = value;
}

ipair dfs (int node, int parent, int upper_road) {
    ipair fmx_and_smx = { - 1e9, - 1e9 };

    int sum_of = 0;

    for (const auto &road : tree[node]) if (road.first != parent) {
        ipair result = dfs(road.first, node, road.second);

        int maxv = max(result.first, result.second);
        int othv = result.first;

        int delta = othv - maxv + road.second;

        sum_of += maxv;

        update(fmx_and_smx, delta);
    }

    int r0 = sum_of + max(0ll, fmx_and_smx.first + fmx_and_smx.second);
    int r1 = sum_of + max(0ll, fmx_and_smx.first + upper_road);
    return { max(r0, 0ll), max(r1, 0ll) };
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> N;
    tree.resize(N);

    for (int iR = 1; iR < N; iR ++) {
        int a, b, c;
        cin >> a >> b >> c;
        a --; b --;

        tree[a].push_back({ b, c });
        tree[b].push_back({ a, c });
    }

    pair<int, int> result = dfs(0, -1, 0);
    cout << result.first << endl;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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