Submission #955751

#	Time	Username	Problem	Language	Result	Execution time	Memory
955751		caterpillow	Road Closures (APIO21_roads)	C++17	24 / 100	2089 ms	21588 KiB

roads

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e12;

int n;
vt<vt<pl>> adj;
vt<ll> ans;

pl dfs(int u, int k, int par = -1) { // {take parent edge, dont take parent edge}
    vt<ll> diff;
    ll take_cost = 0;

    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        auto [take, dont_take] = dfs(v, k, u);
        take_cost += dont_take;
        diff.pb(take - dont_take + w);
    }


    ll dont_take_cost = take_cost;
    ll req = adj[u].size() - k;

    sort(all(diff));

    int i = 0;
    while (i < diff.size() && diff[i] < 0) {
        dont_take_cost += diff[i];
        take_cost += diff[i];
        i++;
    }

    for (; i < req - 1; i++) {
        dont_take_cost += diff[i];
        take_cost += diff[i];
    }

    if (i == req - 1) {
        if (diff.size() <= req - 1) {
            dont_take_cost += INF;
        } else {
            dont_take_cost += diff[req - 1];
        }
    }

    return {take_cost, dont_take_cost};
}


vt<ll> minimum_closure_costs(int _n, vt<int> u, vt<int> v, vt<int> w) {

    n = _n;
    adj.resize(n);
    F0R (i, n - 1) {
        adj[u[i]].pb({v[i], w[i]});
        adj[v[i]].pb({u[i], w[i]});
    }
    ans.resize(n);

    ROF (k, 0, n) {
        ans[k] = dfs(0, k).s;
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'pl dfs(int, int, int)':
roads.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while (i < diff.size() && diff[i] < 0) {
      |            ~~^~~~~~~~~~~~~
roads.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   53 |         if (diff.size() <= req - 1) {
      |             ~~~~~~~~~~~~^~~~~~~~~~

• 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