Submission #916724

#	Time	Username	Problem	Language	Result	Execution time	Memory
916724		green_gold_dog	Road Closures (APIO21_roads)	C++17	12 / 100	146 ms	52564 KiB

roads

//#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;
                      }
                }
        }
        if (dp[v].first.size() < tree[v].size()) {
                dp[v].first.resize(tree[v].size(), 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;
                      }
                }
                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

Compilation message (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:121:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'long long unsigned int' [-Wsign-compare]
  121 |                       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:149: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]
  149 |         for (ll i = 0; i < u.size(); i++) {
      |                        ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22