Submission #1114452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114452		vladilius	Road Closures (APIO21_roads)	C++17	5 / 100	2074 ms	198228 KiB

roads

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W){
    vector<pii> g[n + 1];
    ll tot = 0;
    for (int i = 0; i < n - 1; i++){
        int u = U[i] + 1, v = V[i] + 1, w = W[i];
        g[u].pb({v, w});
        g[v].pb({u, w});
        tot += w;
    }
    
    vector<ll> dp[n + 1];
    vector<int> ch[n + 1];
    vector<int> :: iterator it;
    auto get = [&](int v, int k){
        it = upper_bound(ch[v].begin(), ch[v].end(), k);
        int i = (int) (it - ch[v].begin()) - 1;
        return dp[v][i];
    };
    
    function<void(int, int)> dfs = [&](int v, int pr){
        if ((g[v].size() + !pr) == 1){
            dp[v] = {0};
            ch[v] = {0};
            return;
        }
        for (auto [i, w]: g[v]){
            if (i == pr) continue;
            dfs(i, v);
        }
        
        vector<int> all1;
        for (auto [i, w]: g[v]){
            if (i == pr) continue;
            for (int j: ch[i]){
                all1.pb(j);
                all1.pb(j + 1);
            }
        }
        sort(all1.begin(), all1.end());
        vector<int> all;
        int i = 0;
        while (i < all1.size()){
            int j = i;
            while (j < all1.size() && all1[i] == all1[j]){
                j++;
            }
            all.pb(all1[i]);
            i = j;
        }
        
        ch[v].pb(0); dp[v].pb(0);
        for (int t = 1; t < all.size(); t++){
            int k = all[t]; int R = (t == (all.size() - 1)) ? n : (all[t + 1] - 1);
            ll sum = 0;
            vector<ll> arr;
            for (auto [i, w]: g[v]){
                if (i == pr) continue;
                sum += get(i, k);
                arr.pb(get(i, k - 1) - get(i, k) + w);
            }
            sort(arr.begin(), arr.end(), greater<ll>());
            for (int j = 0; j < min((int) arr.size(), k); j++){
                if (arr[j] <= 0) break;
                sum += arr[j];
            }
            ch[v].pb(k);
            dp[v].pb(sum);
            for (int j = k; j < min((int) arr.size(), R); j++){
                if (arr[j] <= 0) break;
                sum += arr[j];
                ch[v].pb(j + 1);
                dp[v].pb(sum);
            }
        }
    };
    dfs(1, 0);
    
    vector<ll> out;
    for (int i = 0; i < n; i++){
        out.pb(tot - get(1, i));
    }
    return out;
}

Compilation message (stderr)

roads.cpp: In lambda function:
roads.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         while (i < all1.size()){
      |                ~~^~~~~~~~~~~~~
roads.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             while (j < all1.size() && all1[i] == all1[j]){
      |                    ~~^~~~~~~~~~~~~
roads.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int t = 1; t < all.size(); t++){
      |                         ~~^~~~~~~~~~~~
roads.cpp:61:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             int k = all[t]; int R = (t == (all.size() - 1)) ? n : (all[t + 1] - 1);
      |                                      ~~^~~~~~~~~~~~~~~~~~~

• 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