Submission #1283628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283628		behrad	Construction of Highway (JOI18_construction)	C++17	100 / 100	178 ms	24884 KiB

construction

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, fen[maxn], C[maxn], par[maxn], hd[maxn], h[maxn], big[maxn], sz[maxn];
vector<int> comp, g[maxn];
pii E[maxn];
vector<pii> stk[maxn];

void PreDfs(int v) {
  sz[v] = 1;
  for (int& u : g[v]) {
    h[u] = h[v] + 1;
    par[u] = v;
    g[u].erase(find(g[u].begin(), g[u].end(), v));
    PreDfs(u);
    sz[v] += sz[u];
    if (!big[v] || sz[u] > sz[big[v]]) big[v] = u, swap(g[v][0], u);
  }
}

void dfsHld(int v) {
  for (int u : g[v]) {
    if (u == big[v]) hd[u] = hd[v];
    else hd[u] = u;
    dfsHld(u);
  }
}

inline void add(int p, int x) {
  for (; p <= n + 2 ; p += p & -p) fen[p] += x;
}

inline int get(int p) {
  int res = 0;
  for (; p ; p -= p & -p) res += fen[p];
  return res;
}

inline ll calc(vector<pii>& vec) {
  ll res = 0;
  for (auto [v, l] : vec) {
    res += 1ll * l * get(v - 1);
    add(v, l);
  }
  for (auto [v, l] : vec) add(v, -l);
  return res;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n;
  comp.reserve(n);
  for (int i = 1 ; i <= n ; i ++) cin >> C[i], comp.pb(C[i]);
  for (int i = 1 , u , v ; i < n ; i ++) {
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
    E[i] = {u, v};
  }
  cerr << "done\n";
  sort(comp.begin(), comp.end());
  comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
  for (int i = 1 ; i <= n ; i ++) C[i] = lower_bound(comp.begin(), comp.end(), C[i]) - comp.begin() + 1;
  
  par[1] = 1;
  PreDfs(1);
  hd[1] = 1;
  dfsHld(1);

  stk[1].pb({h[1], C[1]});

  for (int i = 1 ; i < n ; i ++) {
    vector<pii> vec, cur;
    int v = E[i].ss;
    while (v != 1) {
      v = par[v];
      int r = hd[v], prv = h[r] - 1;
      while (stk[r].size() && stk[r].back().ff <= h[v]) {
        cur.pb({stk[r].back().ss, stk[r].back().ff - prv});
        prv = stk[r].back().ff;
        stk[r].pop_back();
      }
      if (stk[r].size() && prv < h[v]) cur.pb({stk[r].back().ss, h[v] - prv});
      stk[r].pb({h[v], C[E[i].ss]});

      v = r;
      while (cur.size()) {
        vec.pb(cur.back());
        cur.pop_back();
      }
    }
    stk[hd[E[i].ss]] = {{h[E[i].ss], C[E[i].ss]}};
    cout << calc(vec) << nl;
  }
}

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