제출 #566741

#제출 시각아이디문제언어결과실행 시간메모리
566741Ooops_sorry도로 폐쇄 (APIO21_roads)C++14
7 / 100
2095 ms59400 KiB
#include<bits/stdc++.h> #ifndef LOCAL #include "roads.h" #endif #define ld long double #define ll long long #define pb push_back using namespace std; const int N = 1e5 + 10; const ll INF = 1e18; vector<pair<int,ll>> g[N]; ll e[N], val[N]; map<int, pair<ll, ll>> dp[N]; int k, n; void dfs(int v, int p) { vector<int> arr; ll sum = 0; int r = -1; for (auto to : g[v]) { if (to.first != p) { e[to.first] = to.second; dfs(to.first, v); arr.pb(to.first); } } sort(arr.begin(), arr.end(), [&](int a, int b){return dp[a].size() > dp[b].size();}); int sz = arr.size(); if (arr.size() > 0 && dp[arr[0]].size() > arr.size() + 1) { swap(dp[v], dp[arr[0]]); r = arr[0]; sz = (int)(dp[v].size()) - 1; } for (int i = 0; i <= (int)arr.size(); i++) { ll sum = 0; vector<int> mas; for (auto to : arr) { int need = to; if (to == r) { need = v; } if (dp[need].find(i) == dp[need].end()) { assert(need != v); sum += e[need]; mas.pb(-e[need]); continue; } sum += dp[need][i].first + e[to]; mas.pb({dp[need][i].second - (dp[need][i].first + e[to])}); } sort(mas.begin(), mas.end()); if (arr.size() < i) { for (auto to : mas) { if (to > 0) break; sum += to; } dp[v][i].first = dp[v][i].second = sum; } else if (i == 0) { dp[v][i].first = sum; } else { dp[v][i].second = sum; for (int j = 1; j <= i; j++) { sum += mas[j - 1]; if (j < i) { dp[v][i].second = min(dp[v][i].second, sum); } else { dp[v][i].first = min(dp[v][i].second, sum); } } } } } void zhfs(int v, int p) { for (auto to : g[v]) { if (to.first != p) { zhfs(to.first, v); val[v] += to.second + val[to.first]; } } } vector<long long> minimum_closure_costs(int N, vector<int> u, vector<int> v, vector<int> w) { n = N; ll sum = 0; for (int i = 0; i < n - 1; i++) { g[u[i]].pb({v[i], w[i]}); g[v[i]].pb({u[i], w[i]}); sum += w[i]; } vector<ll> ans; zhfs(0, -1); dfs(0, -1); for (int i = 0; i < n; i++) { if (i < dp[0].size()) { ans.pb(dp[0][i].first); } else { ans.pb(0); } } return ans; } #ifdef LOCAL int main() { int N; assert(1 == scanf("%d", &N)); std::vector<int> U(N - 1), V(N - 1), W(N - 1); for (int i = 0; i < N - 1; ++i) { assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i])); } std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W); for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) { if (i > 0) { printf(" "); } printf("%lld",closure_costs[i]); } printf("\n"); return 0; } #endif

컴파일 시 표준 에러 (stderr) 메시지

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:52:40: warning: narrowing conversion of '(dp[need].std::map<int, std::pair<long long int, long long int> >::operator[](i).std::pair<long long int, long long int>::second - (dp[need].std::map<int, std::pair<long long int, long long int> >::operator[](i).std::pair<long long int, long long int>::first + e[to]))' from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} [-Wnarrowing]
   52 |             mas.pb({dp[need][i].second - (dp[need][i].first + e[to])});
roads.cpp:55:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         if (arr.size() < i) {
      |             ~~~~~~~~~~~^~~
roads.cpp:21:8: warning: unused variable 'sum' [-Wunused-variable]
   21 |     ll sum = 0;
      |        ^~~
roads.cpp:31:9: warning: variable 'sz' set but not used [-Wunused-but-set-variable]
   31 |     int sz = arr.size();
      |         ^~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         if (i < dp[0].size()) {
      |             ~~^~~~~~~~~~~~~~
#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...