Submission #742151

#	Time	Username	Problem	Language	Result	Execution time	Memory
742151		Jarif_Rahman	Road Closures (APIO21_roads)	C++17	24 / 100	2092 ms	20416 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, k;
vector<vector<pair<int, int>>> tree;
vector<ll> dp[2];
vector<ll> pe;

void pre_dfs(int nd, int ss){
    for(auto [x, w]: tree[nd]) if(x != ss) pre_dfs(x, nd), pe[x] = w;
}

void dfs(int nd, int ss){
    ll sum = 0;
    vector<int> o;
    for(auto [x, w]: tree[nd]) if(x != ss) dfs(x, nd), sum+=dp[1][x], o.pb(x);

    dp[0][nd] = sum, dp[1][nd] = sum;

    sort(o.begin(), o.end(), [&](int a, int b){
        return -dp[1][a]+dp[0][a]+pe[a] > -dp[1][b]+dp[0][b]+pe[b];
    });
    
    for(int i = k; i < o.size(); i++) dp[0][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
    for(int i = 0; i < min(k, int(o.size())); i++) if(-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]] < 0)
        dp[0][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
    for(int i = k-1; i < o.size(); i++) dp[1][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
    for(int i = 0; i < min(k-1, int(o.size())); i++) if(-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]] < 0)
        dp[1][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
}

vector<ll> minimum_closure_costs(int _n, vector<int> U, vector<int> V, vector<int> W){
    swap(n, _n);
    tree.resize(n);
    pe.resize(n);

    for(int i = 0; i < n-1; i++){
        tree[U[i]].pb({V[i], W[i]});
        tree[V[i]].pb({U[i], W[i]});
    }

    pre_dfs(0, -1);

    vector<ll> ans(n, 0);
    for(k = 0; k < n; k++){
        if(k == 0){
            for(int x: W) ans[k]+=x;
            continue;
        }

        fill(dp, dp+2, vector<ll>(n, 0));
        dfs(0, -1);
        ans[k] = dp[0][0];
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = k; i < o.size(); i++) dp[0][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
      |                    ~~^~~~~~~~~~
roads.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = k-1; i < o.size(); i++) dp[1][nd]+=-dp[1][o[i]]+dp[0][o[i]]+pe[o[i]];
      |                      ~~^~~~~~~~~~

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