Submission #1047844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047844		Marco_Escandon	Road Closures (APIO21_roads)	C++11	0 / 100	2103 ms	28496 KiB

roads

//#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
ll n;
vector<vector<pair<ll,ll>>> cad;
ll k;
vector<vector<ll>> cache;
ll sol(ll node,ll B, ll P)
{
    if(B>k) return 1e14;
    if(cache[node][B]!=-1) return cache[node][B];
    vector<pair<ll,ll>> asd;
    for(auto i:cad[node])
    {
        if(i.x==P) continue;
        asd.push_back({sol(i.x,1,node),i.y+sol(i.x,0,node)});
    }
    if(asd.size()==0) return cache[node][B]=0;
    vector<ll> dp(min((ll)asd.size()+1,k-B+1),1e14);
    vector<ll> dp2=dp;
    dp[0]=0;
    for(int i=0; i<asd.size(); i++)
    {
        dp2.assign(dp.size(),1e14);
        for(int j=dp.size()-1; j>-1; j--)
        {
            dp2[j]=dp[j]+asd[i].y;
            if(j>0) dp2[j]=min(dp[j-1]+asd[i].x,dp2[j]);
            if(j>0)dp2[j]=min(dp2[j],dp2[j-1]);
        }
        swap(dp,dp2);
    }
    if(k-B>=dp.size()) return cache[node][B]=dp.back();
    return cache[node][B]=dp[k-B];
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,std::vector<int> V,std::vector<int> W) {
    n=N;
    cad.resize(n+1);
    for(int i=0; i<n-1; i++)
    {
        cad[U[i]].push_back({V[i],W[i]});
        cad[V[i]].push_back({U[i],W[i]});
    }
    vector<ll> s(n,0);
    for(int i=0; i<n; i++)
    {
        k=i;
        cache.assign(n,{-1,-1});
        s[i]=sol(0,0,-1);
        if(i>0) s[i]=min(s[i],s[i-1]);
    }
    return s;
}

Compilation message (stderr)

roads.cpp: In function 'll sol(ll, ll, ll)':
roads.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0; i<asd.size(); i++)
      |                  ~^~~~~~~~~~~
roads.cpp:36:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(k-B>=dp.size()) return cache[node][B]=dp.back();
      |        ~~~^~~~~~~~~~~

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