Submission #569827

#	Time	Username	Problem	Language	Result	Execution time	Memory
569827		Lobo	Road Closures (APIO21_roads)	C++17	0 / 100	80 ms	21092 KiB

roads

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n;
vector<pair<int,int>> g[maxn];
int dp[maxn][2], mark[maxn][2];

//fl = 1 -> o anterior ta usado
int sol(int u, int fl) {
    if(mark[u][fl]) return dp[u][fl];
    mark[u][fl] = 1;
    if(u == n) {
        if(fl) return dp[u][fl] = 0;
        return dp[u][fl] = inf;
    }
    int v = u+1;

    int w;
    for(auto V : g[u]) if(V.fr == v) {
        w = V.sc;
    }

    if(fl) dp[u][fl] = min(dp[u][fl],sol(v,0));
    dp[u][fl] = min(dp[u][fl], w+sol(v,1));
    return dp[u][fl];
}

vector<int> minimum_closure_costs(int32_t N, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
    n = N;
    int sm = 0;
    for(int i = 0; i < n-1; i++) {
        g[U[i]+1].pb(mp(V[i]+1,W[i]));
        g[V[i]+1].pb(mp(U[i]+1,W[i]));
        sm+= W[i];
    }
    vector<int> ans;
    ans.pb(sm);
    ans.pb(sol(1,0));
    for(int i = 2; i <= n-1; i++) ans.pb(0);
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'long long int sol(long long int, long long int)':
roads.cpp:38:33: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |     dp[u][fl] = min(dp[u][fl], w+sol(v,1));
      |                                ~^~~~~~~~~

• 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