Submission #650417

#	Time	Username	Problem	Language	Result	Execution time	Memory
650417		Alexandruabcde	Road Closures (APIO21_roads)	C++14	0 / 100	34 ms	6340 KiB

roads

#include "roads.h"

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

using namespace std;

constexpr int NMAX = 205;
typedef long long LL;
constexpr LL INF = 1LL * 1e17;

struct muchie {
    int x, y;
    LL cost;
};

muchie E[NMAX];

int N_glb;
vector <int> G[NMAX];

LL dp[NMAX][NMAX][NMAX];
LL prefMin[NMAX][NMAX][NMAX];

int GrMax[NMAX];
LL aux[NMAX][NMAX];

void Dfs (int Node, int dad = -1) {
    GrMax[Node] = 0;

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

        if (to == dad) continue;

        Dfs(to, Node);
        GrMax[Node] = max(GrMax[Node], GrMax[to]);
    }

    GrMax[Node] = max(GrMax[Node], (int)G[Node].size() - (dad != -1));

    int pos_gr = 0;

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

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

        for (int i = 0; i <= pos_gr; ++ i ) {
            for (int M = i; M <= GrMax[Node]; ++ M ) {
                aux[i][M] = INF;

                for (int j = 1; j <= G[to].size() && j <= M && i > 0; ++ j )
                    aux[i][M] = min(aux[i][M], prefMin[Node][i-1][M] + prefMin[to][j-1][M]);

                for (int j = 0; j < G[to].size() && j <= M && i < pos_gr; ++ j )
                    aux[i][M] = min(aux[i][M], prefMin[Node][i][M] + prefMin[to][j][M] + E[it].cost);
            }
        }

        for (int i = 0; i <= pos_gr; ++ i )
            for (int M = i; M <= GrMax[Node]; ++ M )
                dp[Node][i][M] = aux[i][M];

        for (int i = 0; i <= pos_gr; ++ i )  {
            prefMin[Node][i][i] = dp[Node][i][i];

            for (int j = i+1; j <= GrMax[Node]; ++ j )
                prefMin[Node][i][j] = min(prefMin[Node][i][j-1], dp[Node][i][j]);
        }
    }

    GrMax[Node] = max(GrMax[Node], (int)G[Node].size());
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    N_glb = N;

    for (int i = 1; i < N; ++ i ) {
        E[i] = {U[i-1], V[i-1], W[i-1]};

        G[U[i-1]].push_back(i);
        G[V[i-1]].push_back(i);
    }

    Dfs(0);

    vector <LL> ans;

    for (int i = 0; i < N; ++ i ) {
        ans.push_back(INF);
        for (int j = 0; j <= i; ++ j )
            ans[i] = min(ans[i], dp[0][j][i]);
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void Dfs(int, int)':
roads.cpp:54:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 for (int j = 1; j <= G[to].size() && j <= M && i > 0; ++ j )
      |                                 ~~^~~~~~~~~~~~~~~
roads.cpp:57:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 for (int j = 0; j < G[to].size() && j <= M && i < pos_gr; ++ j )
      |                                 ~~^~~~~~~~~~~~~~

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