제출 #744522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744522		t6twotwo	도로 폐쇄 (APIO21_roads)	C++17	36 / 100	613 ms	220360 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1E18;
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    if (N <= 2000) {
        vector<vector<pair<int, int>>> adj(N);
        for (int i = 0; i < N - 1; i++) {
            adj[U[i]].emplace_back(V[i], W[i]);
            adj[V[i]].emplace_back(U[i], W[i]);
        }
        vector dp(N, vector(N, vector<ll>(2, inf)));
        auto dfs = [&](auto dfs, int x, int p) -> void {
            dp[x][0][0] = 0;
            vector<pair<int, int>> ch;
            for (auto [y, z] : adj[x]) {
                if (y == p) {
                    continue;
                }
                dfs(dfs, y, x);
                dp[x][0][0] += dp[y][0][0] + z;
                ch.emplace_back(y, z);
            }
            for (int i = 1; i < N; i++) {
                int cnt = ch.size();
                ll sum = 0;
                for (auto [y, z] : ch) {
                    sum += dp[y][i][1];
                }
                if (cnt <= i - 1) {
                    dp[x][i][1] = sum;
                }
                if (cnt <= i) {
                    dp[x][i][0] = sum;
                }
                vector<ll> v;
                for (auto [y, z] : ch) {
                    v.push_back(z + dp[y][i][0] - dp[y][i][1]);
                }
                sort(v.begin(), v.end());
                for (int j = 0; j < v.size(); j++) {
                    sum += v[j];
                    cnt--;
                    if (cnt <= i - 1) {
                        dp[x][i][1] = min(dp[x][i][1], sum);
                    }
                    if (cnt <= i) {
                        dp[x][i][0] = min(dp[x][i][0], sum);
                    }
                }
            }
        };
        dfs(dfs, 0, -1);
        vector<ll> ans(N);
        for (int i = 0; i < N; i++) {
            ans[i] = dp[0][i][0];
        }
        return ans;
    }
    if (U == vector<int>(N - 1)) {
        vector<ll> ans(N);
        sort(W.begin(),  W.end());
        for (int i = 0; i < N - 1; i++) {
            ans[N - i - 2] = ans[N - i - 1] + W[i];
        }
        return ans;
    }
    ll dp0 = 0, dp1 = 0;
    for (int i = 0; i < N; i++) {
        ll pd0 = dp0;
        dp0 = max(dp0, dp1);
        dp1 = W[i] + pd0;
    }
    vector<ll> ans(N);
    ans[0] = accumulate(W.begin(), W.end(), 0LL);
    ans[1] = ans[0] - max(dp0, dp1);
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In lambda function:
roads.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 for (int j = 0; j < v.size(); j++) {
      |                                 ~~^~~~~~~~~~
roads.cpp: In instantiation of 'minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23, int, int)> [with auto:23 = minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23, int, int)>]':
roads.cpp:54:23:   required from here
roads.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

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