Submission #375887

#	Time	Username	Problem	Language	Result	Execution time	Memory
375887		KoD	Beads and wires (APIO14_beads)	C++17	28 / 100	1091 ms	748 KiB

beads

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F &&f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    int N;
    std::cin >> N;
    Vec<Vec<std::pair<int, int>>> graph(N);
    for (int i = 1; i < N; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a -= 1;
        b -= 1;
        graph[a].emplace_back(b, c);
        graph[b].emplace_back(a, c);
    }
    Vec<int> t1(N), t2(N);
    const auto dfs = RecLambda([&](const auto dfs, const int u, const int p) -> void {
        Vec<int> a, b;
        for (const auto [v, c]: graph[u]) {
            if (v == p) {
                continue;
            }
            dfs(v, u);
            a.push_back(t1[v] + c);
            b.push_back(std::max(t1[v], t2[v] + c));
        }
        t1[u] = std::accumulate(b.begin(), b.end(), 0);
        t2[u] = std::numeric_limits<int>::min();
        for (int i = 0; i < (int) a.size(); ++i) {
            t2[u] = std::max(t2[u], t1[u] - b[i] + a[i]);
        }
    });
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        dfs(i, -1);
        ans = std::max(ans, t1[i]);
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43