Submission #735208

#	Time	Username	Problem	Language	Result	Execution time	Memory
735208		vjudge1	Beads and wires (APIO14_beads)	C++17	100 / 100	389 ms	33376 KiB

beads

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

#define int int64_t

int32_t 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>> f(2, vector<int>(n, 0));
        function<void(int, int)> dfs = [&](int u, int p) {
                f[1][u] = -1e10;
                f[0][u] = 0;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        dfs(v, u);
                        f[0][u] += max<int>(f[0][v], f[1][v] + c);
                }
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first;
                        int c = e.second;
                        if (v == p) continue;
                        f[1][u] = max<int>(f[1][u], f[0][u] - max<int>(f[0][v], f[1][v] + c) + f[0][v] + c);
                }
        };

        int res = 0;

        function<void(int, int)> reroot = [&](int u, int p) {
                // re-calc f[u]
                int ff0 = f[0][u];
                int ff1 = f[1][u];
                f[0][u] = 0;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        f[0][u] += max<int>(f[0][v], f[1][v] + c);
                }
                vector<int> bestf(2, -1e10);
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        bestf.emplace_back(f[0][u] - max<int>(f[0][v], f[1][v] + c) + f[0][v] + c);
                        int i = bestf.size() - 1;
                        while (i > 0 && bestf[i] > bestf[i - 1]) swap(bestf[i], bestf[i - 1]), i--;
                        bestf.pop_back();
                }
                f[1][u] = bestf[0];
                // update result
                vector<int> best;
                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        best.emplace_back(f[0][v] + c - max<int>(f[0][v], f[1][v] + c));
                        int i = best.size() - 1;
                        while (i > 0 && best[i] > best[i - 1]) swap(best[i], best[i - 1]), i--;
                        if (best.size() > 2) best.pop_back();
                }
                if (best.size() == 2) res = max<int>(res, f[0][u] + max<int>(0, best[0] + best[1]));
                // move to the next one

                for (pair<int, int>& e : adj[u]) {
                        int v = e.first, c = e.second;
                        if (v == p) continue;
                        int f0 = f[0][u];
                        f[0][u] -= max<int>(f[0][v], f[1][v] + c);
                        f[1][u] = bestf[0] == (f[0][u] + f[0][v] + c) ? bestf[1] : bestf[0];
                        f[1][u] -= max<int>(f[0][v], f[1][v] + c);
                        reroot(v, u);
                        f[1][u] = bestf[0];
                        f[0][u] = f0;
                }
                f[0][u] = ff0;
                f[1][u] = ff1;
        };

        dfs(0, -1);
        reroot(0, -1);

        cout << res;
}

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