Submission #429053

#	Time	Username	Problem	Language	Result	Execution time	Memory
429053		Sorting	Road Closures (APIO21_roads)	C++17	24 / 100	2075 ms	22556 KiB

roads

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

using namespace std;

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

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);
        if(dp[to][1] == INF){
            sum += dp[to][0] + w;
            continue;
        }
        sum += dp[to][1];
        diff.push_back(dp[to][0] + w - dp[to][1]);
    }

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

    return ans;
}

Compilation message (stderr)

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

• 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