제출 #428982

#제출 시각아이디문제언어결과실행 시간메모리
428982Sorting도로 폐쇄 (APIO21_roads)C++17
0 / 100
2088 ms21284 KiB
#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; }

컴파일 시 표준 에러 (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;
      |         ^~~
#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...