Submission #757081

#	Time	Username	Problem	Language	Result	Execution time	Memory
757081		thimote75	Beads and wires (APIO14_beads)	C++14	0 / 100	1 ms	212 KiB

beads

#include <bits/stdc++.h>

using namespace std;

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 + fmx_and_smx.first + fmx_and_smx.second;
    int r1 = sum_of + fmx_and_smx.first + upper_road;
    return { max(r0, 0), max(r1, 0) };
}

int 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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43