Submission #732904

#	Time	Username	Problem	Language	Result	Execution time	Memory
732904		vjudge1	Beads and wires (APIO14_beads)	C++17	28 / 100	111 ms	596 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>> f(2, vector<int>(n, 0));
        function<void(int, int)> dfs = [&](int u, int p) {
                f[1][u] = -2e9;
                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(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(f[1][u], f[0][u] - max(f[0][v], f[1][v] + c) + f[0][v] + c);
                }
                if (p == -1) {
                        vector<int> best;
                        for (pair<int, int>& e : adj[u]) {
                                int v = e.first;
                                int c = e.second;
                                if (v == p) continue;
                                best.emplace_back(f[0][v] + c - max(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) f[0][u] += max(0, best[0] + best[1]);
                }
        };

        int res = 0;
        vector<int> random(n);
        iota(random.begin(), random.end(), 0);
        random_shuffle(random.begin(), random.end());
        random_shuffle(random.begin(), random.end());
        random_shuffle(random.begin(), random.end());
        for (int i = 0; i < min(555, n); i++) dfs(random[i], -1), res = max(res, f[0][random[i]]);
        cout << res;
}

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