이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |