Submission #971277

#	Time	Username	Problem	Language	Result	Execution time	Memory
971277		Pannda	Road Closures (APIO21_roads)	C++17	24 / 100	2025 ms	1048576 KiB

roads

#include "roads.h"

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

vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) {

    vector<vector<array<int, 2>>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        auto [u, v, w] = array<int, 3>{U[i], V[i], W[i]};
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<vector<array<long long, 2>>> f(n);
    auto dfs = [&](auto self, int u, int p) -> void {
        int K = n - 1;
        f[u].resize(K + 1);
        vector<long long> sum(K + 1, 0);
        vector<vector<long long>> delta(K + 1);
        for (auto [v, w] : adj[u]) {
            if (v == p) continue;
            self(self, v, u);
            for (int k = 1; k <= K; k++) {
                sum[k] += f[v][k][1];
                delta[k].push_back(f[v][k][0] + w - f[v][k][1]);
            }
        }
        int num_childs = adj[u].size() - (p != -1);
        for (int k = 1; k <= K; k++) {
            sort(delta[k].begin(), delta[k].end());
            int i = 0;
            while (i < delta[k].size() && delta[k][i] < 0) i++;
            f[u][k][0] = sum[k] + accumulate(delta[k].begin(), delta[k].begin() + max(i, num_childs - k), 0LL);
            f[u][k][1] = sum[k] + accumulate(delta[k].begin(), delta[k].begin() + max(i, num_childs + 1 - k), 0LL);
        }
    };
    dfs(dfs, 0, -1);

    vector<long long> res(n);
    res[0] = accumulate(W.begin(), W.end(), 0LL);
    for (int k = 1; k < n; k++) {
        res[k] = f[0][k][0];
    }

    return res;

}

Compilation message (stderr)

roads.cpp: In lambda function:
roads.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             while (i < delta[k].size() && delta[k][i] < 0) i++;
      |                    ~~^~~~~~~~~~~~~~~~~
roads.cpp: In instantiation of 'minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23, int, int)> [with auto:23 = minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23, int, int)>]':
roads.cpp:38:19:   required from here
roads.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22