Submission #732799

#	Time	Username	Problem	Language	Result	Execution time	Memory
732799		vjudge1	Beads and wires (APIO14_beads)	C++17	0 / 100	1 ms	304 KiB

beads

#include <bits/stdc++.h>
using namespace std;

int main() {
        int n;
        cin >> n;
        if (n <= 2) return cout << 0, 0;
        vector<vector<pair<int, int>>> adj(n);
        for (int i = 0; i < n - 1; i++) {
                int a, b, c;
                cin >> a >> b >> c;
                a--, b--;
                adj[a].emplace_back(b, c);
                adj[b].emplace_back(a, c);
        }
        vector<vector<int>> g(2, vector<int>(n, 0));
        function<void(int, int)> dfs = [&](int u, int p) {
                g[0][u] = 0;
                g[1][u] = -1e9;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        dfs(v, u);
                        g[0][u] += max(g[0][v], g[1][v] + c);
                }

                vector<int> best;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        g[1][u] = max(g[1][u], g[0][u] - max(g[0][v], g[1][v] + c) + (g[0][v] + c));
                        best.emplace_back(g[0][v] + c - max(g[0][v], g[1][v] + c));
                        int j = best.size() - 1;
                        while (j > 0 && best[j] > best[j - 1]) swap(best[j], best[j - 1]), j--;
                        if (best.size() > 2) best.pop_back();
                }
                if (best.size() == 2) g[0][u] += max(0, best[0] + best[1]);
        };
        int res = 0;
        for (int i = 0; i < n; i++) dfs(i, -1), res = max(res, g[0][i]);
        cout << res;
}

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