oj.uz

Submission #650703

# Submission time Handle Problem Language Result Execution time Memory
650703 2022-10-14T18:20:18 Z Alexandruabcde Road Closures (APIO21_roads) C++14
0 / 100
 2000 ms 24236 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;

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

    if (dad == -1) {
        dp[Node][1] = sum;
        for (int i = 0; i < max(0, grad - k); ++ 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];

        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 2664 KB Output is correct
2 Correct 817 ms 3032 KB Output is correct
3 Correct 965 ms 3036 KB Output is correct
4 Correct 862 ms 3176 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 4 ms 2644 KB Output is correct
7 Correct 4 ms 2644 KB Output is correct
8 Correct 562 ms 2988 KB Output is correct
9 Correct 894 ms 2892 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Execution timed out 2090 ms 9756 KB Time limit exceeded
13 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 2079 ms 24236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 11236 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 2080 ms 11236 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 2664 KB Output is correct
2 Correct 817 ms 3032 KB Output is correct
3 Correct 965 ms 3036 KB Output is correct
4 Correct 862 ms 3176 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 4 ms 2644 KB Output is correct
7 Correct 4 ms 2644 KB Output is correct
8 Correct 562 ms 2988 KB Output is correct
9 Correct 894 ms 2892 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Execution timed out 2090 ms 9756 KB Time limit exceeded
13 Halted 0 ms 0 KB -