Submission #1120024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120024		abczz	Road Closures (APIO21_roads)	C++17	12 / 100	190 ms	82504 KiB

roads

#include "roads.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long

using namespace std;

array<ll, 2> operator+(array<ll, 2> a, array<ll, 2> b) {
  return {a[0]+b[0], a[1]+b[1]};
};
struct SegTree{
  vector <array<ll, 2>> st;
  vector <array<ll, 2>> X;
  void init(ll x) {
    st.resize(4*x);
  }
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = {X[l][0], 1};
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = st[id*2] + st[id*2+1];
  }
  void update(ll id, ll l, ll r, ll q, array<ll, 2> w) {
    if (l == r) {
      st[id] = w;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    st[id] = st[id*2] + st[id*2+1];
  }
  ll query(ll id, ll l, ll r, ll w) {
    if (l == r) {
      if (!w) return 0;
      else if (st[l][1] == w) return st[id][0];
      else return 1e18;
    }
    ll mid = (l+r)/2;
    if (st[id*2][1] <= w) return st[id*2][0] + query(id*2+1, mid+1, r, w-st[id*2][1]);
    else return query(id*2, l, mid, w);
  }
}ST[100000];
vector <ll> A;
bool B[100000], E[100000];
ll dp[100000][2], k, f, t;
vector <ll> deg[100000];
vector <array<ll, 2>> X[100000];
map <ll, ll> mp[100000];
vector <ll> F;
vector <array<ll, 2> > adj[100000];

//0 -> only remaining k-1, 1 -> only remaining k
void dfs(ll u, ll p) {
  B[u] = 1;
  vector <ll> S;
  ll res = 0, a = 1e18, b = 1e18, z = 0, tot = X[u].size() - (p != -1);
  for (auto [v, x] : adj[u]) {
    if (v == p) continue;
    dfs(v, u);
    res += dp[v][0];
    S.push_back(dp[v][1]-dp[v][0]+x);
    --tot, ++z;
  }
  a = min(a, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-(k-1))));
  b = min(b, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-k)));
  //cout << res << ":" << a << " " << b << " " << X[u].size() << " " << k << endl;
  sort(S.begin(), S.end());
  for (int i=0; i<S.size(); ++i) {
    res += S[i];
    --z;
    a = min(a, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-(k-1))));
    b = min(b, res+ST[u].query(1, 0, ST[u].X.size()-1, max(0LL, tot+z-k)));
  }
  dp[u][0] = a, dp[u][1] = b;
  //cout << u << " " << dp[u][0] << " " << dp[u][1] << endl;
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
  for (int i=0; i<N-1; ++i) {
    X[U[i]].push_back({W[i], V[i]});
    X[V[i]].push_back({W[i], U[i]});
    t += W[i];
  }
  for (int i=0; i<N; ++i) {
    sort(X[i].begin(), X[i].end(), [](auto a, auto b) {
      return a[0] < b[0];
    });
    for (int j=0; j<X[i].size(); ++j) {
      mp[i][X[i][j][1]] = j;
    }
    ST[i].init(X[i].size());
    ST[i].X = X[i];
    ST[i].build(1, 0, X[i].size()-1);
    deg[X[i].size()-1].push_back(i);
  }
  k = N-1;
  for (int i=0; i<N-1; ++i) {
    f = 0;
    for (auto u : deg[k]) {
      E[u] = 1;
      A.push_back(u);
      for (auto [x, y] : X[u]) {
        if (E[y]) {
          adj[u].push_back({y, x});
          adj[y].push_back({u, x});
          ST[u].update(1, 0, ST[u].X.size()-1, mp[u][y], {0, 0});
          ST[y].update(1, 0, ST[y].X.size()-1, mp[y][u], {0, 0});
        }
      }
    }
    for (auto u : A) B[u] = dp[u][0] = dp[u][1] = 0;
    for (auto u : A) {
      if (!B[u]) {
        dfs(u, -1);
        f += dp[u][1];
      }
    }
    F.push_back(f);
    --k;
  }
  F.push_back(t);
  reverse(F.begin(), F.end());
  return F;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(long long int, long long int)':
roads.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int i=0; i<S.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:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int j=0; j<X[i].size(); ++j) {
      |                   ~^~~~~~~~~~~~
roads.cpp:122:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  122 |     for (auto u : A) B[u] = dp[u][0] = dp[u][1] = 0;
      |                             ~~~~~~~~~^~~~~~~~~~~~~~

• 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