Submission #429053

#TimeUsernameProblemLanguageResultExecution timeMemory
429053SortingRoad Closures (APIO21_roads)C++17
24 / 100
2075 ms22556 KiB
#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;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...