Submission #31608

#	Time	Username	Problem	Language	Result	Execution time	Memory
31608		user202729	Beads and wires (APIO14_beads)	C++14	28 / 100	223 ms	1040 KiB

beads

// https://oj.uz/problem/view/APIO14_beads

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
//typedef std::pair<int,int> ii;

struct dp{
    int dp0, dp1;
    dp(int dp0, int dp1) : dp0(dp0), dp1(dp1) {};
};

struct edge{
    int vertex, weight;
    edge(int vertex, int weight) : vertex(vertex), weight(weight) {};
};

std::vector<std::vector<edge>> adjlist;
std::vector<int> parent;

dp dfs(int node) {
    int p = parent[node];
    adjlist[node].erase(
        std::remove_if(adjlist[node].begin(), adjlist[node].end(), [p, node](edge x){return x.vertex == parent[node];}),
        adjlist[node].end()
    );
    dp result (0, -9999999);
    for (edge e : adjlist[node]) {
        parent[e.vertex] = node;
        dp tmp = dfs(e.vertex);
        int val = std::max(tmp.dp0, tmp.dp1 + e.weight);
        result.dp0 += val;
        result.dp1 = std::max(result.dp1, e.weight + tmp.dp0 - val);
    }
    result.dp1 += result.dp0;
    return result;
}

int main() {
    int n;
    std::cin >> n;
    adjlist.resize(n);
    for (int i = 1; i < n; ++i) {
        int u, v, val;
        std::cin >> u >> v >> val;
        --u; --v;
        adjlist[u].emplace_back(v, val);
        adjlist[v].emplace_back(u, val);
    }

    std::mt19937 engine ((std::random_device())());
    std::vector<int> roots (n);
    for (int i = 0; i < n; ++i) roots[i] = i;
    std::shuffle(roots.begin(), roots.end(), engine);
    if (roots.size() > 500) roots.resize(500);

    int result = -1;
    for (int root : roots) {
        parent.assign(n, -1);
        auto bkp_adjlist = adjlist;
        result = std::max(result, dfs(root).dp0);
        adjlist = std::move(bkp_adjlist);
    }

    std::cout << result << '\n';
}

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