Submission #428982

#	Time	Username	Problem	Language	Result	Execution time	Memory
428982		Sorting	Road Closures (APIO21_roads)	C++17	0 / 100	2088 ms	21284 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 3;

int n;
vector<pair<int, int>> adj[N];
vector<ll> ans;
ll dp[N][2];//0 for removed edge

void solve(int u, int k, int par = -1){
    ll sum = 0;
    vector<ll> diff;
    for(auto [to, w]: adj[u]){
        if(to == par) continue;
        solve(to, k, u);
        sum += dp[to][0];
        diff.push_back(dp[to][1] + w - dp[to][0]);
    }

    sort(diff.begin(), diff.end());
    int cnt = 0, i;
    for(i = 0; i < diff.size() && (diff[i] < 0 || diff.size() - i > k + 1); ++i)
        sum += diff[i];
    dp[u][0] = sum;
    if(diff.size() - i > k)
        dp[u][1] = sum + diff[i];
    else
        dp[u][1] = sum;
}

vector<long long> minimum_closure_costs(int _n, vector<int> _u, vector<int> _v, vector<int> _w) {
    n = _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]});
    }

    ans.resize(n, 0);
    for(int k = 0; k < n; ++k){
        solve(0, k);
        ans[k] = dp[0][1];
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void solve(int, int, int)':
roads.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(i = 0; i < diff.size() && (diff[i] < 0 || diff.size() - i > k + 1); ++i)
      |                ~~^~~~~~~~~~~~~
roads.cpp:26:67: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     for(i = 0; i < diff.size() && (diff[i] < 0 || diff.size() - i > k + 1); ++i)
      |                                                   ~~~~~~~~~~~~~~~~^~~~~~~
roads.cpp:29:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     if(diff.size() - i > k)
      |        ~~~~~~~~~~~~~~~~^~~
roads.cpp:25:9: warning: unused variable 'cnt' [-Wunused-variable]
   25 |     int cnt = 0, i;
      |         ^~~

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