Submission #440406

#	Time	Username	Problem	Language	Result	Execution time	Memory
440406		sam571128	Road Closures (APIO21_roads)	C++17	12 / 100	91 ms	13064 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>

#define ll long long

using namespace std;

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    vector<vector<pair<int,int>>> adj;
    adj.resize(N);

    bool star = true, chain = true;

    int arr[N];

    for(int i = 0;i < N-1;i++){
        adj[U[i]].push_back({V[i],W[i]});
        adj[V[i]].push_back({U[i],W[i]});
        arr[U[i]+1] = W[i];
        if(U[i]!=0) star = false;
        if(U[i]+1!=V[i]) chain = false;
    }

    vector<ll> cost(N,0);

    if(star){
        sort(W.begin(),W.end());
        ll now = 0;
        for(int i = 0;i < N-1;i++){
            now += W[i];
            cost[N-2-i] = now;
        }
        return cost;
    }

    if(chain){
        ll dp[N][2] = {}, sum = 0;
        for(int i = 1;i <= N-1;i++){
            dp[i][0] = dp[i-1][1];
            dp[i][1] = min(dp[i-1][1],dp[i-1][0])+arr[i];
            sum += arr[i];
        }
        cost[0] = sum, cost[1] = min(dp[N-1][0],dp[N-1][1]);
        return cost;
    }

    return cost;
}


//X 2 X 3 X 4 X 5 X

• 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