Submission #1345174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345174		nagorn_ph	Road Closures (APIO21_roads)	C++20	5 / 100	29 ms	10412 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int32_t, int32_t>
#define tiii tuple <int32_t, int32_t, int32_t>
#define all(a) a.begin(), a.end()

using namespace std;

const int32_t N = 1e5 + 5;
const int32_t inf = 1e9;

int32_t n;
vector <pii> adj[N];

std::vector<long long> minimum_closure_costs(int32_t N, std::vector<int32_t> u,
                                             std::vector<int32_t> v,
                                             std::vector<int32_t> w) {
    n = N;
    
    for (int32_t i = 0; i < n - 1; i++) {
        adj[u[i]].emb(w[i], v[i]);
        adj[v[i]].emb(w[i], u[i]);
    }
    sort(all(w));
    vector <int> ans; ans.emb(0);
    for (int32_t i = 1; i < n; i++) ans.emb(ans.back() + w[i - 1]);
    reverse(all(ans));
    return ans;
}

• Subtask 1: 5 / 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