Submission #875869

#	Time	Username	Problem	Language	Result	Execution time	Memory
875869		awu	Construction of Highway (JOI18_construction)	C++14	100 / 100	1626 ms	31972 KiB

construction

#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #define int long long
#define ll long long
// #define double long double
#define all(x) x.begin(), x.end()
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
#define f first
#define s second
// #define endl '\n'

using pii = pair<int, int>;

const int inf = 1 << 30;
// const ll inf = 1ll << 62;

pii t[262144];
int n;
void init(int s) {
  n = 1;
  while(n < s) n *= 2;
}
void update(int i, pii v) {
  for(t[i += n] = v; i > 1; i /= 2) {
    t[i / 2] = max(t[i], t[i ^ 1]);
  }
}
pii query(int l, int r) {
  pii res = {-1, -1};
  for(l += n, r += n; l < r; l /= 2, r /= 2) {
    if(l & 1) res = max(res, t[l++]);
    if(r & 1) res = max(res, t[--r]);
  }
  return res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n;
  vector<int> c(n);
  for(int i = 0; i < n; i++) {
    cin >> c[i];
  }
  vector<pii> el;
  vector<vector<int>> ch(n);
  for(int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b; a--; b--;
    ch[a].push_back(b);
    el.push_back({a, b});
  }
  vector<int> d(n);
  vector<vector<int>> jmp(n, vector<int>(ceil(log2(n))));
  vector<int> tin(n), tout(n);
  int time = 0;
  function<void(int)> dfs = [&](int cur) {
    tin[cur] = time++;
    for(int i = 1; i < log2(n); i++) {
      jmp[cur][i] = jmp[jmp[cur][i - 1]][i - 1];
    }
    for(auto i : ch[cur]) {
      jmp[i][0] = cur;
      d[i] = d[cur] + 1;
      dfs(i);
    }
    tout[cur] = time;
  };
  dfs(0);
  init(n);
  update(0, {-1, c[0]});
  for(int i = 0; i < n - 1; i++) {
    vector<pii> v;
    int cur = el[i].f;
    while(true) {
      int od = d[cur];
      pii curv = query(tin[cur], tout[cur]);
      for(int i = ceil(log2(n)) - 1; i >= 0; i--) {
        int nxt = jmp[cur][i];
        if(query(tin[nxt], tout[nxt]).f == curv.f) {
          cur = nxt;
        }
      }
      v.push_back({curv.s, od - d[cur] + 1});
      if(cur == 0) break;
      cur = jmp[cur][0];
    }
    int ans = 0;
    function<vector<pii>(int, int)> dnc = [&](int l, int r) {
      if(l + 1 == r) return vector<pii>{v[l]};
      int m = (l + r) / 2;
      auto lv = dnc(l, m), rv = dnc(m, r);
      vector<pii> res;
      int i = 0, j = 0, x = 0;
      while(j < rv.size()) {
        if(i < lv.size() && lv[i].f < rv[j].f) {
          res.push_back(lv[i]);
          x += lv[i].s;
          i++;
        } else {
          res.push_back(rv[j]);
          ans += x * rv[j].s;
          j++;
        }
      }
      while(i < lv.size()) {
        res.push_back(lv[i]);
        i++;
      }
      return res;
    };
    dnc(0, v.size());
    cout << ans << '\n';
    update(tin[el[i].s], {i, c[el[i].s]});
  }
}

Compilation message (stderr)

construction.cpp: In lambda function:
construction.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |       while(j < rv.size()) {
      |             ~~^~~~~~~~~~~
construction.cpp:97:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         if(i < lv.size() && lv[i].f < rv[j].f) {
      |            ~~^~~~~~~~~~~
construction.cpp:107:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |       while(i < lv.size()) {
      |             ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84