Submission #650700

#	Time	Username	Problem	Language	Result	Execution time	Memory
650700		Alexandruabcde	Road Closures (APIO21_roads)	C++14	14 / 100	2073 ms	18384 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];
LL aux[NMAX];

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

    for (int i = 0; i <= k; ++ i )
        aux[i] = 0;

    aux[0] = 0;
    int grad = 0;

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

        if (to == dad) continue;
        ++ grad;

        aux[grad] = aux[grad-1] + dp[to][0];

        for (int cnt = min(grad-1, k); cnt >= 0; -- cnt ) {
            ///       elimin muchia Node -> to;  NU elimin muchia Node -> to
            aux[cnt] = aux[cnt] + dp[to][1];
            if (cnt > 0) aux[cnt] = min(aux[cnt], aux[cnt-1] + dp[to][0]);
        }
    }

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

    if (k > 0) {
        dp[Node][0] = aux[min(grad, k-1)];

        for (int i = 0; i <= min(grad, k-1); ++ i )
            dp[Node][0] = min(dp[Node][0], aux[i]);
    }

    if (dad == -1) {
        dp[Node][1] = aux[min(grad, k)];
        for (int i = 0; i <= min(grad, k); ++ i )
            dp[Node][1] = min(dp[Node][1], aux[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] = aux[min(grad, k)] + E[it].cost;
        for (int i = 0; i <= min(grad, k); ++ i )
            dp[Node][1] = min(dp[Node][1], aux[i] + E[it].cost);

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

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