Submission #859564

#	Time	Username	Problem	Language	Result	Execution time	Memory
859564		boris_mihov	Road Closures (APIO21_roads)	C++17	0 / 100	23 ms	54876 KiB

roads

#include "roads.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

int n;
std::vector <std::pair <int,int>> g[MAXN];
bool blR[MAXN][MAXN][2];
llong dpR[MAXN][MAXN][2];
bool blC[MAXN][MAXN][MAXN];
llong dpC[MAXN][MAXN][MAXN];

void firstDFS(int node, int par)
{
    for (auto &curr : g[node])
    {
        if (curr.first == par)
        {
            std::swap(curr, g[node].back());
            g[node].pop_back();
            break;
        }
    }

    for (const auto &[u, w] : g[node])
    {
        firstDFS(u, node);
    }
}

llong fRoot(int, int, bool);
llong fChildren(int, int, int);

llong fChildren(int node, int idx, int k, int k2)
{
    if (idx == -1)
    {
        return 0;
    }

    int u = g[node][idx].first;
    int w = g[node][idx].second;
    if (blC[u][k][k2])
    {
        return dpC[u][k][k2];
    }

    blC[u][k][k2] = true;
    dpC[u][k][k2] = INF;

    if (k < idx + 1) dpC[u][k][k2] = fChildren(node, idx - 1, k, k2) + fRoot(u, k2 - 1, true);
    if (k > 0) dpC[u][k][k2] = std::min(dpC[u][k][k2], fChildren(node, idx - 1, k - 1, k2) + fRoot(u, k2, false) + w);
    return dpC[u][k][k2];
}

llong fRoot(int node, int k, bool k2)
{
    // if (k == 1) std::cout << "call: " << node << ' ' << g[node].size() << ' ' << k << '\n';
    if (g[node].empty())
    {
        if (k >= g[node].size()) return 0;
        return INF;
    }

    if (blR[node][k][k2])
    {
        return dpR[node][k][k2];
    }

    blR[node][k][k2] = true;
    dpR[node][k][k2] = fChildren(node, g[node].size() - 1, std::max(0, (int)g[node].size() - k), k + k2);
    return dpR[node][k][k2];
}

std::vector <llong> minimum_closure_costs(int N, std::vector <int> U, std::vector <int> V, std::vector <int> W)
{
    n = N;
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        g[U[i] + 1].push_back({V[i] + 1, W[i]});
        g[V[i] + 1].push_back({U[i] + 1, W[i]});
    }

    firstDFS(1, 0);
    std::vector <llong> ans(n);
    for (int i = 0 ; i < n ; ++i)
    {
        ans[i] = fRoot(1, i, false);
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'llong fRoot(int, int, bool)':
roads.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (k >= g[node].size()) return 0;
      |             ~~^~~~~~~~~~~~~~~~~

• 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