oj.uz

Submission #650700

# Submission time Handle Problem Language Result Execution time Memory
650700 2022-10-14T18:12:45 Z Alexandruabcde Road Closures (APIO21_roads) C++14
14 / 100
 2000 ms 18384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 2073 ms 2896 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 2065 ms 18384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 4 ms 2664 KB Output is correct
7 Correct 4 ms 2636 KB Output is correct
8 Correct 5 ms 2644 KB Output is correct
9 Correct 4 ms 2644 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2664 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 5 ms 2644 KB Output is correct
14 Correct 7 ms 2644 KB Output is correct
15 Correct 8 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 4 ms 2644 KB Output is correct
18 Correct 5 ms 2644 KB Output is correct
19 Correct 6 ms 2644 KB Output is correct
20 Correct 7 ms 2660 KB Output is correct
21 Correct 2 ms 2664 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 4 ms 2644 KB Output is correct
6 Correct 4 ms 2664 KB Output is correct
7 Correct 4 ms 2636 KB Output is correct
8 Correct 5 ms 2644 KB Output is correct
9 Correct 4 ms 2644 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2664 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Correct 5 ms 2644 KB Output is correct
14 Correct 7 ms 2644 KB Output is correct
15 Correct 8 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 4 ms 2644 KB Output is correct
18 Correct 5 ms 2644 KB Output is correct
19 Correct 6 ms 2644 KB Output is correct
20 Correct 7 ms 2660 KB Output is correct
21 Correct 2 ms 2664 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 254 ms 2804 KB Output is correct
24 Correct 948 ms 2924 KB Output is correct
25 Correct 625 ms 2840 KB Output is correct
26 Correct 999 ms 2876 KB Output is correct
27 Correct 1475 ms 3028 KB Output is correct
28 Correct 1537 ms 3004 KB Output is correct
29 Correct 799 ms 2892 KB Output is correct
30 Correct 993 ms 2900 KB Output is correct
31 Correct 1006 ms 2900 KB Output is correct
32 Execution timed out 2040 ms 3036 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 11848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 11848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Execution timed out 2073 ms 2896 KB Time limit exceeded
3 Halted 0 ms 0 KB -