Submission #375892

#	Time	Username	Problem	Language	Result	Execution time	Memory
375892		KoD	Beads and wires (APIO14_beads)	C++17	100 / 100	415 ms	48096 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)...);
    }
};

constexpr int INF = 2000000000;

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<Vec<int>> a(N), b(N);
    for (int i = 0; i < N; ++i) {
        a[i].resize(graph[i].size());
        b[i].resize(graph[i].size());
    }
    RecLambda([&](const auto dfs, const int u, const int p) -> std::pair<int, int> {
        int sum = 0, dif = INF;
        for (int i = 0; i < (int) graph[u].size(); ++i) {
            const auto [v, c] = graph[u][i];
            if (v == p) {
                continue;
            }
            const auto [t1, t2] = dfs(v, u);
            a[u][i] = t1 + c;
            b[u][i] = std::max(t1, t2 + c);
            sum += b[u][i];
            dif = std::min(dif, b[u][i] - a[u][i]);
        }
        return std::make_pair(sum, sum - dif);
    })(0, -1);
    int ans = 0;
    RecLambda([&](const auto dfs, const int u, const int p, const int up_t1, const int up_t2) -> void {
        const auto size = (int) graph[u].size();
        int sum = 0;
        for (int i = 0; i < size; ++i) {
            const auto [v, c] = graph[u][i];
            if (v == p) {
                a[u][i] = up_t1 + c;
                b[u][i] = std::max(up_t1, up_t2 + c);
            }
            sum += b[u][i];
        }
        ans = std::max(ans, sum);
        Vec<int> pref(size + 1, INF);
        Vec<int> suff(size + 1, INF);
        for (int i = 0; i < size; ++i) {
            pref[i + 1] = std::min(pref[i], b[u][i] - a[u][i]);
            suff[i + 1] = std::min(suff[i], b[u][size - i - 1] - a[u][size - i - 1]);
        }
        for (int i = 0; i < size; ++i) {
            const auto [v, c] = graph[u][i];
            if (v == p) {
                continue;
            }
            const auto t1 = sum - b[u][i];
            const auto t2 = t1 - std::min(pref[i], suff[size - i - 1]);
            dfs(v, u, t1, t2);
        }
    })(0, -1, 0, 0);
    std::cout << ans << '\n';
    return 0;
}

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