Submission #569820

#	Time	Username	Problem	Language	Result	Execution time	Memory
569820		Lobo	Road Closures (APIO21_roads)	C++17	14 / 100	1217 ms	1048576 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 = 2200;

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

int sol(int u, int q, int id, int ant, int k) {
    if(mark[u][q][id] == k) return dp[u][q][id];
    mark[u][q][id] = k;

    if(id == g[u].size()) {
        if(q > k) return dp[u][q][id] = inf;
        return dp[u][q][id] = 0;
    }

    int v = g[u][id].fr;
    int w = g[u][id].sc;
    if(v == ant) {
        return dp[u][q][id] = sol(u,q,id+1,ant,k);
    }
    return dp[u][q][id] = min(sol(u,q,id+1,ant,k)+sol(v,g[v].size(),0,u,k),w+sol(u,q-1,id+1,ant,k)+sol(v,g[v].size()-1,0,u,k));
}

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];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n+1; j++) {
            for(int k = 0; k <= g[i].size()+10; k++) {
                dp[i][j].pb(0);
                mark[i][j].pb(0);
            }
        }
    }
    vector<int> ans;
    ans.pb(sm);
    for(int i = 1; i <= n-1; i++) {
        ans.pb(sol(1,g[1].size(),0,0,i));
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'long long int sol(long long int, long long int, long long int, long long int, long long int)':
roads.cpp:26:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(id == g[u].size()) {
      |        ~~~^~~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:49:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int k = 0; k <= g[i].size()+10; k++) {
      |                            ~~^~~~~~~~~~~~~~~~~

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