Submission #842625

#	Time	Username	Problem	Language	Result	Execution time	Memory
842625		WLZ	Truck Driver (IOI23_deliveries)	C++17	100 / 100	1149 ms	47160 KiB

deliveries

#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll LINF = (ll) 1e18;

struct node {
  int l, r;
  ll sum_t, sum_t_w, max_w, lazy;
  node *left, *right;
} *root;

node *build(int l, int r, const vector<int> &t, const vector<ll> &w) {
  if (l == r) return new node{l, r, t[l], t[l] * w[l], w[l], 0, 0, 0};
  node *left = build(l, (l + r) / 2, t, w), *right = build((l + r) / 2 + 1, r, t, w);
  return new node{l, r, left->sum_t + right->sum_t, left->sum_t_w + right->sum_t_w, max(left->max_w, right->max_w), 0, left, right};
}

void push(node *cur) {
  if (cur->lazy == 0) return;
  cur->sum_t_w += cur->lazy * cur->sum_t;
  cur->max_w += cur->lazy;
  if (cur->left) {
    cur->left->lazy += cur->lazy;
    cur->right->lazy += cur->lazy;
  }
  cur->lazy = 0;
}

void update(node *cur, int l, int r, int val) {
  push(cur);
  if (cur->l > r || cur->r < l) return;
  if (l <= cur->l && cur->r <= r) {
    cur->lazy += val;
    push(cur);
    return;
  }
  update(cur->left, l, r, val); update(cur->right, l, r, val);
  cur->sum_t = cur->left->sum_t + cur->right->sum_t;
  cur->sum_t_w = cur->left->sum_t_w + cur->right->sum_t_w;
  cur->max_w = max(cur->left->max_w, cur->right->max_w);
}

ll query(node *cur, int l, int r) {
  push(cur);
  if (cur->l > r || cur->r < l) return 0;
  if (l <= cur->l && cur->r <= r) return cur->sum_t_w;
  return query(cur->left, l, r) + query(cur->right, l, r);
}

int n, cur_hld_pos = 0;
ll pre_ans = 0, sum_w = 0;
vector<int> p, w, subtree_size, heavy, up_edge, hld_head, hld_pos, hld_rev_pos;
vector<ll> subtree_sum, depth;
vector< vector< pair<int, int> > > g;

int find_last_large(node *cur) {
  push(cur);
  if (cur->l == cur->r) return hld_rev_pos[cur->l];
  push(cur->left); push(cur->right);
  if (2ll * cur->right->max_w > sum_w + 1) return find_last_large(cur->right);
  return find_last_large(cur->left);
}

void dfs(int u) {
  subtree_size[u] = 1;
  subtree_sum[u] = w[u];
  for (auto &[v, t] : g[u]) {
    if (v == p[u]) continue;
    up_edge[v] = t;
    depth[v] = depth[u] + t;
    p[v] = u;
    dfs(v); 
    subtree_sum[u] += subtree_sum[v];
    subtree_size[u] += subtree_size[v];
    if (heavy[u] == -1 || subtree_size[v] > subtree_size[heavy[u]]) heavy[u] = v;
  }
}

void hld_decompose(int u, int head) {
  hld_head[u] = head;
  hld_rev_pos[cur_hld_pos] = u;
  hld_pos[u] = cur_hld_pos++;
  if (heavy[u] != -1) hld_decompose(heavy[u], head);
  for (auto &[v, t] : g[u]) {
    if (v != p[u] && v != heavy[u]) hld_decompose(v, v);
  }
}

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
  n = N; w = W; g.resize(n);
  for (int i = 0; i < n - 1; i++) {
    g[U[i]].push_back({V[i], T[i]});
    g[V[i]].push_back({U[i], T[i]});
  }
  p.assign(n, -1); subtree_size.resize(n); heavy.assign(n, -1); up_edge.assign(n, 0); depth.assign(n, 0); subtree_sum.assign(n, 0);
  dfs(0);
  hld_pos.reserve(n); hld_rev_pos.reserve(n); hld_head.resize(n);
  hld_decompose(0, 0);
  vector<int> hld_t(n); vector<ll> hld_w(n);
  for (int i = 0; i < n; i++) {
    hld_t[hld_pos[i]] = up_edge[i];
    hld_w[hld_pos[i]] = subtree_sum[i];
    pre_ans += subtree_sum[i] * up_edge[i];
    sum_w += w[i];
  }
  root = build(0, n - 1, hld_t, hld_w);
}

long long max_time(int S, int X) {
  int diff = X - w[S]; w[S] = X;
  pre_ans += (ll) diff * depth[S];
  sum_w += diff;
  int u = S;
  while (u != -1) {
    update(root, hld_pos[hld_head[u]], hld_pos[u], diff);
    u = p[hld_head[u]];
  }
  u = find_last_large(root);
  ll ans = pre_ans + depth[u] * (sum_w + 1);
  while (u != -1) {
    ans -= 2ll * query(root, hld_pos[hld_head[u]], hld_pos[u]);
    u = p[hld_head[u]];
  }
  return 2ll * ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36