Submission #650705

#	Time	Username	Problem	Language	Result	Execution time	Memory
650705		Alexandruabcde	Road Closures (APIO21_roads)	C++14	31 / 100	2072 ms	34896 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];
vector <int> Degree[NMAX];
vector <int> GoodNodes;
bool Unlocked[NMAX];
LL dp[NMAX][2];
bool viz[NMAX];

void Dfs (int k, int Node, int dad = -1) {
    viz[Node] = true;

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

        if (to == dad) continue;
        if (viz[to]) continue;
        if (!Unlocked[to]) 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;
        if (Unlocked[to]) {
            V.push_back(dp[to][1] - dp[to][0]);
            sum += dp[to][0];
        }
        else {
            V.push_back(E[it].cost);
        }
    }

    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;
    }
}

LL Solve (int K) {
    LL ans = 0;
    for (auto it : GoodNodes) {
        if (viz[it]) continue;

        Dfs(K, it, -1);
        ans += dp[it][1];
    }

    for (auto it : GoodNodes)
        viz[it] = false;

    return ans;
}

void Add (int Node) {
    GoodNodes.push_back(Node);
    Unlocked[Node] = true;
}

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);
    }

    for (int i = 0; i < N; ++ i ) {
        Degree[G[i].size()].push_back(i);
    }

    vector <LL> ans;
    ans.resize(N);

    for (int k = N-1; k >= 0; -- k ) {
        ans[k] = Solve(k);

        for (auto it : Degree[k])
            Add(it);
    }

    return ans;
}

Compilation message (stderr)

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

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