제출 #757102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757102		thimote75	구슬과 끈 (APIO14_beads)	C++14	0 / 100	1 ms	212 KiB

beads

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