제출 #916766

#제출 시각아이디문제언어결과실행 시간메모리
916766green_gold_dog도로 폐쇄 (APIO21_roads)C++17
31 / 100
2090 ms52076 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx") #include <bits/stdc++.h> #include "roads.h" using namespace std; typedef long long ll; typedef double db; typedef long double ldb; typedef complex<double> cd; constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007; constexpr db PI = acos(-1); constexpr bool IS_FILE = false, IS_TEST_CASES = false; random_device rd; mt19937 rnd32(rd()); mt19937_64 rnd64(rd()); template<typename T> bool assign_max(T& a, T b) { if (b > a) { a = b; return true; } return false; } template<typename T> bool assign_min(T& a, T b) { if (b < a) { a = b; return true; } return false; } template<typename T> T square(T a) { return a * a; } template<> struct std::hash<pair<ll, ll>> { ll operator() (pair<ll, ll> p) const { return ((__int128)p.first * MOD + p.second) % INF64; } }; void dfs(ll v, ll p, vector<vector<pair<ll, ll>>>& tree, vector<pair<vector<ll>, vector<ll>>>& dp) { ll rpc = INF32; ll nx = 0; ll ms = 0; for (auto[a, b] : tree[v]) { if (a == p) { rpc = b; } else { dfs(a, v, tree, dp); assign_max(ms, (ll)dp[a].first.size()); } } for (auto[a, b] : tree[v]) { if (a != p) { if (dp[a].first.size() == ms) { swap(dp[a], dp[v]); nx = b; break; } } } while (dp[v].first.size() < tree[v].size()) { dp[v].first.push_back(0); } while (dp[v].second.size() < tree[v].size()) { dp[v].second.push_back(dp[v].first[dp[v].second.size()] + nx); } while (dp[v].second.size() > tree[v].size()) { dp[v].second.pop_back(); } vector<pair<ll, ll>> sons; if (nx != 0) { sons.emplace_back(v, nx); } for (auto[a, b] : tree[v]) { if (!dp[a].first.empty()) { sons.emplace_back(a, b); for (ll j = tree[v].size(); j < dp[a].first.size(); j++) { dp[v].first[j] += dp[a].first[j]; } } } multiset<ll> all; ll ns = 0; for (ll i = 0; i < tree[v].size(); i++) { vector<pair<ll, ll>> nsons; vector<ll> nall; ll na = 0; for (auto[a, b] : sons) { if (dp[a].first.size() > i) { na += dp[a].first[i]; } if (dp[a].second.size() > i) { nall.push_back(dp[a].second[i] - dp[a].first[i]); nsons.emplace_back(a, b); } else { //all.insert(b); //ns += b; nall.push_back(b); nsons.emplace_back(a, b); } } while (all.size() > (tree[v].size() - i)) { ns -= *all.rbegin(); all.erase(all.find(*all.rbegin())); } auto it = all.rbegin(); ll x = all.size(); sort(nall.begin(), nall.end()); na += ns; ll mx = 0; for (auto j : nall) { if (x < (tree[v].size() - i)) { assign_max(mx, j); x++; na += j; } else { if (it != all.rend() && *it > j) { na += j; na -= *it; it--; assign_max(mx, j); } } } if (it != all.rend()) { assign_max(mx, *it); } if (i == 0) { mx = 0; } dp[v].first[i] = na; dp[v].second[i] = na - mx + rpc; assign_min(dp[v].first[i], dp[v].second[i]); sons = nsons; } } vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) { vector<vector<pair<ll, ll>>> tree(n); for (ll i = 0; i < u.size(); i++) { tree[u[i]].emplace_back(v[i], w[i]); tree[v[i]].emplace_back(u[i], w[i]); } vector<pair<vector<ll>, vector<ll>>> dp(n); dfs(0, 0, tree, dp); dp[0].first.resize(n, 0); return dp[0].first; } #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(ll, ll, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<std::pair<std::vector<long long int>, std::vector<long long int> > >&)':
roads.cpp:65:46: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   65 |                       if (dp[a].first.size() == ms) {
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~
roads.cpp:88:53: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                       for (ll j = tree[v].size(); j < dp[a].first.size(); j++) {
      |                                                   ~~^~~~~~~~~~~~~~~~~~~~
roads.cpp:95:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (ll i = 0; i < tree[v].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~
roads.cpp:100:46: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  100 |                       if (dp[a].first.size() > i) {
      |                           ~~~~~~~~~~~~~~~~~~~^~~
roads.cpp:103:47: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  103 |                       if (dp[a].second.size() > i) {
      |                           ~~~~~~~~~~~~~~~~~~~~^~~
roads.cpp:123:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'long long unsigned int' [-Wsign-compare]
  123 |                       if (x < (tree[v].size() - i)) {
      |                           ~~^~~~~~~~~~~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:151:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for (ll i = 0; i < u.size(); 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...