Submission #441129

#	Time	Username	Problem	Language	Result	Execution time	Memory
441129		peijar	Construction of Highway (JOI18_construction)	C++17	100 / 100	679 ms	30420 KiB

construction

#include <bits/stdc++.h>
#define int long long
using namespace std;

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

const int MAXN = 1e5;

vector<int> adj[MAXN];
int par[MAXN], root[MAXN], sz[MAXN], depth[MAXN], heavy[MAXN];
map<pair<int, int>, int> segs[MAXN];
int nbSommets;

Fenwick<int> fen(MAXN);

void dfs(int u) {
  sz[u] = 1;
  for (int v : adj[u]) {
    depth[v] = depth[u] + 1;
    dfs(v);
    sz[u] += sz[v];
  }

  heavy[u] = -1;
  for (int v : adj[u])
    if (2 * sz[v] >= sz[u])
      heavy[u] = v;
}

void dfs2(int u) {
  for (int v : adj[u]) {
    if (heavy[u] == v)
      root[v] = root[u];
    else
      root[v] = v;
    dfs2(v);
  }
}

int query(int iNoeud) { // Go up from iNoeud !
  vector<pair<int, int>> toErase;
  int ret = 0;

  auto pushChange = [&]() {
    auto it = segs[root[iNoeud]].upper_bound(make_pair(depth[iNoeud], 1e18));
    while (it != segs[root[iNoeud]].begin()) {
      it--;
      auto [deb, fin] = it->first;
      int val = it->second;
      int cb = min(depth[iNoeud], fin) - deb + 1;
      ret += cb * fen.sum(val);
      fen.upd(val, cb);
      toErase.emplace_back(val, cb);
    }
  };

  while (root[iNoeud]) {
    pushChange();
    iNoeud = par[root[iNoeud]];
  }
  pushChange();
  for (auto [val, cb] : toErase)
    fen.upd(val, -cb);
  return ret;
}

void upd(int iNoeud, int val) { // change all values above iNoeud !

  auto pullChange = [&]() {
    while (!segs[root[iNoeud]].empty() and
           segs[root[iNoeud]].begin()->first.second <= depth[iNoeud])
      segs[root[iNoeud]].erase(segs[root[iNoeud]].begin());
    if (!segs[root[iNoeud]].empty() and
        depth[iNoeud] < segs[root[iNoeud]].begin()->first.second) {
      auto [deb, fin] = segs[root[iNoeud]].begin()->first;
      auto v = segs[root[iNoeud]].begin()->second;
      segs[root[iNoeud]].erase(segs[root[iNoeud]].begin());
      segs[root[iNoeud]][make_pair(depth[iNoeud] + 1, fin)] = v;
    }
    segs[root[iNoeud]][make_pair(depth[root[iNoeud]], depth[iNoeud])] = val;
  };
  while (root[iNoeud]) {
    pullChange();
    iNoeud = par[root[iNoeud]];
  }
  pullChange();
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> nbSommets;
  vector<int> distinct(nbSommets);
  vector<int> liveliness(nbSommets);
  for (int i = 0; i < nbSommets; ++i) {
    cin >> liveliness[i];
    distinct[i] = liveliness[i];
  }
  sort(distinct.begin(), distinct.end());
  distinct.resize(unique(distinct.begin(), distinct.end()) - distinct.begin());

  for (int i = 0; i < nbSommets; ++i)
    liveliness[i] =
        lower_bound(distinct.begin(), distinct.end(), liveliness[i]) -
        distinct.begin();
  vector<pair<int, int>> edges(nbSommets - 1);
  for (auto &[A, B] : edges) {
    cin >> A >> B;
    --A, --B;
    par[B] = A;
    adj[A].push_back(B);
  }
  dfs(0);
  dfs2(0);

  segs[0][{0, 0}] = liveliness[0];

  for (auto [a, b] : edges) {
    cout << query(a) << '\n';
    upd(b, liveliness[b]);
    /*cout << "==============" << endl;
    for (int i = 0; i < nbSommets; ++i)
      if (i == root[i]) {
        cout << i + 1 << ": ";
        for (auto it : segs[i])
          cout << it.first.first << ' ' << it.first.second << " = "
               << it.second + 1 << ' ';
        cout << endl;
      }*/
  }
}

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