Submission #650704

#	Time	Username	Problem	Language	Result	Execution time	Memory
650704		Alexandruabcde	Road Closures (APIO21_roads)	C++14	24 / 100	2100 ms	24100 KiB

roads

#include "roads.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 100005;
typedef long long LL;
constexpr LL INF = 1LL * 1e15;

struct muchie {
    int x, y;
    LL cost;
};

muchie E[NMAX];

vector <int> G[NMAX];

LL dp[NMAX][2];

void Dfs (int k, int Node, int dad = -1) {
    for (auto it : G[Node]) {
        int to = (E[it].x == Node ? E[it].y : E[it].x);

        if (to == dad) continue;

        Dfs(k, to, Node);
    }

    int grad = 0;
    vector <LL> V;
    LL sum = 0;

    for (auto it : G[Node]) {
        int to = (E[it].x == Node ? E[it].y : E[it].x);

        if (to == dad) continue;

        ++ grad;
        V.push_back(dp[to][1] - dp[to][0]);
        sum += dp[to][0];
    }

    dp[Node][0] = INF;
    dp[Node][1] = INF;

    sort(V.begin(), V.end());

    if (k > 0) {
        dp[Node][0] = sum;
        for (int i = 0; i < max(0, grad - k + 1); ++ i )
            dp[Node][0] += V[i];

        for (int i = max(0, grad - k + 1); i < V.size() && V[i] < 0; ++ i )
            dp[Node][0] += V[i];
    }

    if (dad == -1) {
        dp[Node][1] = sum;
        for (int i = 0; i < max(0, grad - k); ++ i )
            dp[Node][1] += V[i];
        for (int i = max(0, grad - k); i < V.size() && V[i] < 0; ++ i )
            dp[Node][1] += V[i];
    }

    for (auto it : G[Node]) {
        int to = (E[it].x == Node ? E[it].y : E[it].x);

        if (to != dad) continue;

        dp[Node][1] = sum + E[it].cost;
        for (int i = 0; i < max(0, grad - k); ++ i )
            dp[Node][1] += V[i];
        for (int i = max(0, grad - k); i < V.size() && V[i] < 0; ++ i )
            dp[Node][1] += V[i];

        break;
    }
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {

    for (int i = 1; i < N; ++ i ) {
        E[i] = {U[i-1], V[i-1], 1LL * W[i-1]};

        G[U[i-1]].push_back(i);
        G[V[i-1]].push_back(i);
    }

    vector <LL> ans;

    for (int k = 0; k < N; ++ k ) {
        Dfs(k, 0);

        ans.push_back(dp[0][1]);
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void Dfs(int, int, int)':
roads.cpp:56:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = max(0, grad - k + 1); i < V.size() && V[i] < 0; ++ i )
      |                                            ~~^~~~~~~~~~
roads.cpp:64:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i = max(0, grad - k); i < V.size() && V[i] < 0; ++ i )
      |                                        ~~^~~~~~~~~~
roads.cpp:76:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = max(0, grad - k); i < V.size() && V[i] < 0; ++ i )
      |                                        ~~^~~~~~~~~~

• 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