oj.uz

Submission #842625

# Submission time Handle Problem Language Result Execution time Memory
842625 2023-09-03T06:26:13 Z WLZ Truck Driver (IOI23_deliveries) C++17
100 / 100
 1149 ms 47160 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10240 KB Output is correct
2 Correct 81 ms 10084 KB Output is correct
3 Correct 91 ms 10316 KB Output is correct
4 Correct 79 ms 10288 KB Output is correct
5 Correct 80 ms 10400 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 700 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10240 KB Output is correct
2 Correct 81 ms 10084 KB Output is correct
3 Correct 91 ms 10316 KB Output is correct
4 Correct 79 ms 10288 KB Output is correct
5 Correct 80 ms 10400 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 67 ms 4348 KB Output is correct
9 Correct 1149 ms 37924 KB Output is correct
10 Correct 1093 ms 38040 KB Output is correct
11 Correct 1095 ms 37968 KB Output is correct
12 Correct 987 ms 40400 KB Output is correct
13 Correct 932 ms 40440 KB Output is correct
14 Correct 986 ms 40400 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10240 KB Output is correct
2 Correct 81 ms 10084 KB Output is correct
3 Correct 91 ms 10316 KB Output is correct
4 Correct 79 ms 10288 KB Output is correct
5 Correct 80 ms 10400 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 26 ms 4948 KB Output is correct
9 Correct 336 ms 44088 KB Output is correct
10 Correct 373 ms 44064 KB Output is correct
11 Correct 335 ms 43956 KB Output is correct
12 Correct 397 ms 47040 KB Output is correct
13 Correct 363 ms 47160 KB Output is correct
14 Correct 255 ms 43464 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10240 KB Output is correct
2 Correct 81 ms 10084 KB Output is correct
3 Correct 91 ms 10316 KB Output is correct
4 Correct 79 ms 10288 KB Output is correct
5 Correct 80 ms 10400 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 2 ms 700 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 4 ms 604 KB Output is correct
23 Correct 67 ms 4348 KB Output is correct
24 Correct 1149 ms 37924 KB Output is correct
25 Correct 1093 ms 38040 KB Output is correct
26 Correct 1095 ms 37968 KB Output is correct
27 Correct 987 ms 40400 KB Output is correct
28 Correct 932 ms 40440 KB Output is correct
29 Correct 986 ms 40400 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 3 ms 860 KB Output is correct
32 Correct 26 ms 4948 KB Output is correct
33 Correct 336 ms 44088 KB Output is correct
34 Correct 373 ms 44064 KB Output is correct
35 Correct 335 ms 43956 KB Output is correct
36 Correct 397 ms 47040 KB Output is correct
37 Correct 363 ms 47160 KB Output is correct
38 Correct 255 ms 43464 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 4 ms 604 KB Output is correct
41 Correct 31 ms 4776 KB Output is correct
42 Correct 503 ms 41224 KB Output is correct
43 Correct 538 ms 41772 KB Output is correct
44 Correct 459 ms 42672 KB Output is correct
45 Correct 378 ms 43188 KB Output is correct
46 Correct 400 ms 43648 KB Output is correct
47 Correct 512 ms 43688 KB Output is correct
48 Correct 436 ms 44256 KB Output is correct
49 Correct 391 ms 44836 KB Output is correct
50 Correct 370 ms 45192 KB Output is correct
51 Correct 348 ms 45844 KB Output is correct
52 Correct 628 ms 40208 KB Output is correct
53 Correct 681 ms 40204 KB Output is correct
54 Correct 658 ms 40200 KB Output is correct
55 Correct 257 ms 42392 KB Output is correct
56 Correct 276 ms 43056 KB Output is correct
57 Correct 265 ms 43116 KB Output is correct