Submission #441533

#	Time	Username	Problem	Language	Result	Execution time	Memory
441533		Lam_lai_cuoc_doi	도로 폐쇄 (APIO21_roads)	C++17	14 / 100	2090 ms	31948 KiB

roads

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 2e3 + 5;
constexpr ll Inf = 1e17;

int n;
vector<pair<int, ll>> adj[N];
ll dp[N][N];

void dfs(int v, int p, const int &k)
{
    dp[v][0] = 0;
    for (auto i : adj[v])
        if (i.first != p)
        {
            dfs(i.first, v, k);
            for (int j = adj[v].size(); ~j; --j)
                dp[v][j] = min(dp[v][j] + dp[i.first][max(0, (int)adj[i.first].size() - k)], j ? (dp[v][j - 1] + i.second + dp[i.first][max(0, (int)adj[i.first].size() - k - 1)]) : Inf);
        }
    for (int j = n; ~j; --j)
        dp[v][j] = (j > (int)adj[v].size() ? Inf : min(dp[v][j], dp[v][j + 1]));
}

ll f(int k)
{
    fill_n(&dp[0][0], N * N, Inf);
    dfs(1, 1, k);

    return dp[1][max(0, (int)adj[1].size() - k)];
}

vector<ll> minimum_closure_costs(int m, vector<int> u, vector<int> v, vector<int> w)
{
    n = m;
    for (int i = 0; i < n - 1; ++i)
    {
        ++u[i];
        ++v[i];
        adj[u[i]].emplace_back(v[i], w[i]);
        adj[v[i]].emplace_back(u[i], w[i]);
    }
    vector<ll> ans(n);

    for (int i = 0; i < n; ++i)
        ans[i] = f(i);
    return ans;
}

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