Submission #995519

#	Time	Username	Problem	Language	Result	Execution time	Memory
995519		abczz	Construction of Highway (JOI18_construction)	C++17	100 / 100	1036 ms	37432 KiB

construction

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

vector <ll> adj[100000];
array <ll, 2> edge[100000];
vector <ll> dfn;
vector <array<ll, 2>> V;
array <ll, 2> R[100000];
ll n, a, b, x, l, r, d, t, f, C[100000], D[100000], T[100000], bl[100000][17];
struct SegTree{
  vector <ll> st{vector <ll>(400000, 0)};
  void update(ll id, ll l, ll r, ll q) {
    if (l == r) {
      st[id] = T[dfn[l]];
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q);
    else update(id*2+1, mid+1, r, q);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return -1e18;
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
}ST;

void merge_sort(ll l, ll r) {
  if (l == r) return;
  ll mid = (l+r)/2;
  merge_sort(l, mid);
  merge_sort(mid+1, r);
  vector <array<ll, 2>> tmp;
  ll i = l, j = mid+1, s = 0;
  while (i <= mid && j <= r) {
    if (V[i][0] <= V[j][0]) {
      f += V[i][1] * s;
      tmp.push_back(V[i++]);
    }
    else {
      s += V[j][1];
      tmp.push_back(V[j++]);
    }
  }
  while (i <= mid) {
    f += V[i][1] * s;
    tmp.push_back(V[i++]);
  }
  while (j <= r) tmp.push_back(V[j++]);
  for (int i=l; i<=r; ++i) V[i] = tmp[i-l];
}
void dfs(ll u) {
  R[u][0] = dfn.size();
  dfn.push_back(u);
  for (auto v : adj[u]) {
    D[v] = D[u] + 1;
    dfs(v);
  }
  R[u][1] = dfn.size()-1;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> C[i];
  }
  for (int i=1; i<n; ++i) {
    cin >> edge[i][0] >> edge[i][1];
    --edge[i][0], --edge[i][1];
    T[edge[i][1]] = i;
    bl[edge[i][1]][0] = edge[i][0];
    adj[edge[i][0]].push_back(edge[i][1]);
  }
  dfs(0);
  for (int j=1; j<17; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
    }
  }
  for (int i=1; i<n; ++i) {
    V.clear();
    a = edge[i][0];
    while (true) {
      t = ST.query(1, 0, dfn.size()-1, R[a][0], R[a][1]);
      b = a;
      for (int j=16; j>=0; --j) {
        x = ST.query(1, 0, dfn.size()-1, R[bl[b][j]][0], R[bl[b][j]][1]);
        if (x == t) b = bl[b][j];
      }
      V.push_back({C[edge[t][1]], D[a]-D[b]+1});
      if (!b) break;
      else a = bl[b][0];
    }
    f = 0;
    reverse(V.begin(), V.end());
    merge_sort(0, V.size()-1);
    cout << f << '\n';
    ST.update(1, 0, dfn.size()-1, R[edge[i][1]][0]);
  }
}

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