Submission #619539

#	Time	Username	Problem	Language	Result	Execution time	Memory
619539		Jomnoi	Road Closures (APIO21_roads)	C++17	36 / 100	255 ms	12284 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"
using namespace std;

const int MAX_N = 1e5 + 5;

long long dp[MAX_N];
long long dp2[MAX_N][2];
vector <pair <int, int>> graph[MAX_N];

void dfs(int u, int p, int k) {
    vector <long long> opt;
    long long sum = 0;
    for(auto [v, w] : graph[u]) {
        if(v == p) {
            continue;
        }

        dfs(v, u, k);

        sum += dp2[v][0];
        long long cost = -dp2[v][0] + dp2[v][1] + w;
        if(cost > 0) {
            opt.push_back(cost);
        }
    }

    sort(opt.rbegin(), opt.rend());

    dp2[u][0] = dp2[u][1] = sum;
    for(int i = 0; i < min(k - 1, (int)opt.size()); i++) {
        dp2[u][0] += opt[i];
        dp2[u][1] += opt[i];
    }
    if(opt.size() >= k and k > 0) {
        dp2[u][0] += opt[k - 1];
    }
}

vector <long long> minimum_closure_costs(int N, vector <int> U, vector <int> V, vector <int> W) {
    bool subtask1 = true, subtask2 = true;

    for(int i = 0; i < N - 1; i++) {
        graph[U[i]].emplace_back(V[i], W[i]);
        graph[V[i]].emplace_back(U[i], W[i]);

        if(U[i] != 0 and V[i] != 0) {
            subtask1 = false;
        }
        if(U[i] != i or V[i] != i + 1) {
            subtask2 = false;
        }
    }
    
    vector <long long> ans;
    if(subtask1 == true) {
        sort(W.rbegin(), W.rend());

        long long sum = 0;
        for(int i = 0; i < N - 1; i++) {
            sum += W[i];
        }
        for(int i = 0; i < N - 1; i++) {
            ans.push_back(sum);
            sum -= W[i];
        }
        ans.push_back(0);
    }
    else if(subtask2 == true) {
        long long sum = 0;
        for(int i = 0; i < N - 1; i++) {
            sum += W[i];
        }
        ans.push_back(sum);
        
        for(int i = 0; i < N - 1; i++) {
            dp[i] = W[i];
            if(i - 1 >= 0) {
                dp[i] = max(dp[i], dp[i - 1]);
            }
            if(i - 2 >= 0) {
                dp[i] = max(dp[i], dp[i - 2] + W[i]);
            }
        }
        ans.push_back(sum - dp[N - 2]);

        for(int i = 0; i < N - 2; i++) {
            ans.push_back(0);
        }
    }
    else if(N <= 2000) {
        long long sum = 0;
        for(int i = 0; i < N - 1; i++) {
            sum += W[i];
        }

        for(int k = 0; k < N; k++) {
            dfs(0, -1, k);

            ans.push_back(sum - dp2[0][0]);
        }
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int, int)':
roads.cpp:35:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     if(opt.size() >= k and k > 0) {
      |        ~~~~~~~~~~~^~~~

• 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