oj.uz

Submission #650426

# Submission time Handle Problem Language Result Execution time Memory
650426 2022-10-13T17:51:23 Z Alexandruabcde Road Closures (APIO21_roads) C++14
0 / 100
 26 ms 4984 KB 
#include "roads.h"

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

using namespace std;

constexpr int NMAX = 205;
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)];
    if (dad == -1)
        dp[Node][1] = aux[min(grad, k)];

    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;

        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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 26 ms 4380 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 2 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 2 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 4984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 4984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -