Submission #981808

#	Time	Username	Problem	Language	Result	Execution time	Memory
981808		Unforgettablepl	Road Closures (APIO21_roads)	C++17	24 / 100	2087 ms	24108 KiB

roads

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

#define int long long

vector<pair<int,int>> adj[100001];
int DP[100001][2];
int k;

void dfs(int x,int p,int w){
    DP[x][1] = w;
    DP[x][0] = 0;
    int sub = 0;
    vector<int> options;
    for(auto&i:adj[x])if(i.first!=p){
            dfs(i.first,x,i.second);
            sub++;
            DP[x][0]+=DP[i.first][0];
            options.emplace_back(DP[i.first][1]-DP[i.first][0]);
        }
    sort(options.begin(),options.end());
    DP[x][1]+=DP[x][0];
    for(int i=0;i<max(0ll,sub-k+1);i++)DP[x][0]+=options[i];
    for(int i=0;i<max(0ll,sub-k);i++)DP[x][1]+=options[i];
    for(int i=max(0ll,sub-k+1);i<options.size();i++)if(options[i]<0ll)DP[x][0]+=options[i];
    for(int i=max(0ll,sub-k);i<options.size();i++)if(options[i]<0ll)DP[x][1]+=options[i];
}

std::vector<int> minimum_closure_costs(int32_t N, std::vector<int32_t > U,
                                             std::vector<int32_t > V,
                                             std::vector<int32_t > W) {
    int base = 0;
    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]);
        base+=W[i];
    }
    vector<int> ans(N);
    ans[0] = base;
    for(int i=1;i<N;i++){
        k = i;
        dfs(0,-1,0);
        ans[i] = DP[0][1];
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(long long int, long long int, long long int)':
roads.cpp:25:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=max(0ll,sub-k+1);i<options.size();i++)if(options[i]<0ll)DP[x][0]+=options[i];
      |                                ~^~~~~~~~~~~~~~~
roads.cpp:26:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=max(0ll,sub-k);i<options.size();i++)if(options[i]<0ll)DP[x][1]+=options[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