Submission #984213

#	Time	Username	Problem	Language	Result	Execution time	Memory
984213		Alkaser_ID	Road Closures (APIO21_roads)	C++17	12 / 100	62 ms	15520 KiB

roads

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

vector<ll> adj[200005];
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    ll n = N;
    bool sb1 = true, sb2 = true;
    for(int i=0;i<n-1;i++) {
        if(U[i] != 0) sb1 = false;
        if(U[i] != i || V[i] != i+1) sb2 = false;
        ll u = U[i],v = V[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if(sb1){
        vector<ll> f;
        for(ll i=0;i<n-1;++i) f.push_back(W[i]);
        sort(f.begin(),f.end());
        ll res = 0;
        vector<ll> ans;
        ans.push_back(res);
        for(ll i=0;i<n-1;++i){
            res += f[i];
            ans.push_back(res);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
    if(sb2){
        ll sm =0;
        for(ll i=0;i<n-1;++i) sm += W[i];
        vector<ll> ans;
        ans.push_back(sm);
        vector<ll> dp0(n+3,0),dp1(n+3,0);
        dp0[0] = 0; dp1[0] = W[0];
        for(ll i=1;i<n-1;++i){
            dp0[i] = dp1[i-1];
            dp1[i] = min(dp0[i-1],dp1[i-1]) + W[i];
        }
        ans.push_back(min(dp0[n-2],dp1[n-2]));
        for(ll i=2;i<n;++i) ans.push_back(0);
        return ans;
    }
}

/*
5
0 1 1
0 2 4
0 3 3
2 4 2


4
0 1 5
2 0 10
0 3 5

6
0 1 2
1 2 4
2 3 4
3 4 3
4 5 6

*/

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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