Submission #645960

#	Time	Username	Problem	Language	Result	Execution time	Memory
645960		dattranxxx	Construction of Highway (JOI18_construction)	C++11	100 / 100	361 ms	110524 KiB

construction

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
vector<int> adj[N];
int a[N], c[N];
int n;
int siz[N], par[N], dep[N];
int size(int u) {
  siz[u] = 1;
  for (int& v : adj[u]) {
    adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
    par[v] = u, dep[v] = dep[u] + 1;
    siz[u] += size(v);
    if (siz[v] > siz[adj[u][0]])
      swap(v, adj[u][0]);
  }
  return siz[u];
}

int nxt[N];
void hld(int u) {
  for (int v : adj[u]) {
    nxt[v] = v == adj[u][0] ? nxt[u] : v;
    hld(v);
  }
}
int m;
int bit[N];
int cnt(int i) {
  int res = 0;
  for (; i; i -= i & -i)
    res += bit[i];
  return res;
}

void add(int i, int x) {
  for (; i <= m; i += i & -i)
    bit[i] += x;
}

#define Tp pair<int, int>
#define fi first
#define se second
deque<Tp> seq[N];

ll get(int u) {
  vector<Tp> cur;
  for (int v = u; ~v; v = par[nxt[v]]) {
    int len = dep[v] - dep[nxt[v]] + 1;
    vector<Tp> tmp;
    for (auto& p : seq[nxt[v]]) {
      if (len >= p.se)
        len -= p.se, tmp.emplace_back(p);
      else {
        tmp.emplace_back(p);
        tmp.back().se = len; break;
      }
    }
    reverse(tmp.begin(), tmp.end());
    for (auto& p : tmp) cur.emplace_back(p);
  }
  ll res = 0;
  for (auto& p : cur) 
    res += p.se * cnt(p.fi - 1), add(p.fi, p.se);
  for (auto& p : cur) add(p.fi, -p.se);
  return res;
}

void update(int u) {
  for (int v = u; ~v; v = par[nxt[v]]) {
    int len = dep[v] - dep[nxt[v]] + 1;
    while (!seq[nxt[v]].empty()) {
      if (len >= seq[nxt[v]].front().se)
        len -= seq[nxt[v]].front().se, seq[nxt[v]].pop_front();
      else {
        seq[nxt[v]].front().se -= len; break;
      }
    }
    seq[nxt[v]].emplace_front(a[u], dep[v] - dep[nxt[v]] + 1);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> a[i], c[i] = a[i];
  sort(c, c + n); m = unique(c, c + n) - c;
  for (int i = 0; i < n; ++i)
    a[i] = lower_bound(c, c + m, a[i]) - c + 1;
  vector<pair<int, int>> edges;
  for (int i = 0, u, v; i < n-1; ++i)
    cin >> u >> v, u--, v--,
    adj[u].emplace_back(v),
    adj[v].emplace_back(u),
    edges.emplace_back(u, v);
  par[0] = -1, size(0), hld(0);
  update(0);
  for (int i = 0, u, v; i < n-1; ++i) {
    tie(u, v) = edges[i];
    cout << get(u) << '\n';
    update(v);
  }
	return 0;
}

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