Submission #1202393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202393		jer033	Road Closures (APIO21_roads)	C++20	24 / 100	2092 ms	17400 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;
using pil = pair<int, ll>;
const ll INF = 1'000'000'000'000'000'000;

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vector<vector<pil>> edgelist(N);
    for (int i=0; i<(N-1); i++)
    {
        int u = U[i];
        int v = V[i];
        ll w = W[i];
        edgelist[u].push_back({v, w});
        edgelist[v].push_back({u, w});
    }
    //root the tree
    vector<int> bfs_order;
    vector<bool> visited(N, 0);
    vector<vector<pil>> children(N);
    visited[0] = 1;
    bfs_order.push_back(0);
    int total = 1;
    int curr = 0;
    while (curr < total)
    {
        int curr_node = bfs_order[curr];
        curr++;
        for (pil edge: edgelist[curr_node])
        {
            int neigh = edge.first; ll weight = edge.second;
            if (visited[neigh] == 0)
            {
                visited[neigh] = 1;
                bfs_order.push_back(neigh);
                total++;
                children[curr_node].push_back(edge);
            }
        }
    }

    vector<ll> answer_compilation(N, 0);
    for (int allowed = 1; allowed < N; allowed++)
    {
        vector<ll> dp1(N, INF);// can keep allowed
        vector<ll> dp2(N, INF);// can keep allowed - 1
        for (int index = N-1; index>=0; index--)
        {
            int curr_node = bfs_order[index];
            ll total = 0;
            vector<ll> choice;
            for (pil child: children[curr_node])
            {
                int childnode = child.first;
                ll childweight = child.second;
                ll required = dp1[childnode]+childweight;
                ll alternative = dp2[childnode];
                if (alternative < required)
                    choice.push_back(alternative-required);
                total+=required;
            }
            sort(choice.begin(), choice.end());
            int choicesize = choice.size();
            int aa; ll total_benefit;

            aa = min(allowed-1, choicesize);
            total_benefit = 0;
            for (int i=0; i<aa; i++)
                total_benefit = total_benefit+choice[i];
            dp2[curr_node] = total+total_benefit;

            aa = min(allowed, choicesize);
            total_benefit = 0;
            for (int i=0; i<aa; i++)
                total_benefit = total_benefit+choice[i];
            dp1[curr_node] = total+total_benefit;
        }
        answer_compilation[allowed] = min(dp1[0], dp2[0]);
    }

    ll grand_total = 0;
    for (int i=0; i<(N-1); i++)
        grand_total += W[i];
    answer_compilation[0] = grand_total;
    return answer_compilation;

}

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