oj.uz

Submission #623366

# Submission time Handle Problem Language Result Execution time Memory
623366 2022-08-05T13:58:24 Z MilosMilutinovic Designated Cities (JOI19_designated_cities) C++14
100 / 100
 547 ms 57776 KB 
/**
 *    author:  wxhtzdy
 *    created: 05.08.2022 10:18:20
**/
#include <bits/stdc++.h>

using namespace std;

class segtree {
  public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    long long mx = 0;
    long long add = 0;
    int id = 0;
    void apply(int l, int r, long long v) {
      mx += v;
      add += v;
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.mx = max(a.mx, b.mx);
    res.id = (a.mx == res.mx ? a.id : b.id);
    return res;
  }
  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    if (tree[x].add != 0) {
      tree[x + 1].apply(l, y, tree[x].add);
      tree[z].apply(y + 1, r, tree[x].add);
      tree[x].add = 0;
    }
  }
  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }
  int n;
  vector<node> tree;
  void build(int x, int l, int r) {
    tree[x].id = l;
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once
  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<vector<array<int, 3>>> g(n);
  long long total = 0;
  for (int i = 0; i < n - 1; i++) {
    int x, y, w0, w1;
    cin >> x >> y >> w0 >> w1;
    --x; --y;
    g[x].push_back({y, w1, w0});
    g[y].push_back({x, w0, w1});
    total += w0;
    total += w1;
  }                       
  vector<long long> dp(n);
  vector<int> que(1, 0); 
  vector<bool> vis(n);
  vis[0] = true; 
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    for (auto& p : g[i]) {
      int j = p[0];
      if (!vis[j]) {
        dp[0] += p[1];
        que.push_back(j);
        vis[j] = true;
      }
    }
  }       
  vector<long long> down(n);
  function<void(int, int)> Dp = [&](int v, int pr) {
    for (auto& p : g[v]) {
      int u = p[0];
      if (u != pr) {
        dp[u] = dp[v] - p[1] + p[2];
        Dp(u, v);
        down[v] = max(down[v], down[u] + p[2]);
      }
    }
  };
  Dp(0, 0);
  int root = max_element(dp.begin(), dp.end()) - dp.begin();
  vector<long long> ans(n + 1);
  ans[1] = dp[root];
  long long best = -1e18;
  int who = -1;
  function<void(int, int, long long)> Dfs = [&](int v, int pr, long long up) {
    long long me = max(up, down[v]) + dp[v];
    if (me > best) {
      best = me;
      who = v;
    }    
    long long f0 = -1e18;
    long long f1 = -1e18;
    int id = -1;
    for (auto& p : g[v]) {
      long long he = down[p[0]] + p[2];
      if (he > f0) {
        f0 = he;
        id = p[0];
      } else {
        f1 = max(f1, he);
      }
    }
    for (auto& p : g[v]) {
      int u = p[0];
      if (u == pr) {
        continue;
      }
      long long new_up = max(0LL, up);
      if (u != id) {
        new_up = max(new_up, f0);
      } else {
        new_up = max(new_up, f1);
      }
      Dfs(u, v, new_up + p[1]);
    }
  };
  Dfs(0, 0, -1e18);
  root = who;
  vector<int> up(n);
  vector<int> par(n);
  vector<int> tin(n);
  vector<int> tout(n);
  vector<int> ver(n);
  int T = -1;      
  segtree st(n);
  function<void(int, int)> Go = [&](int v, int pr) {
    tin[v] = ++T;
    ver[T] = v;
    par[v] = pr;
    for (auto& p : g[v]) {
      int u = p[0];
      if (u != pr) {
        Go(u, v);
        up[u] = p[2];
        st.modify(tin[u], tout[u], p[2]);
      }
    }
    tout[v] = T;
  };
  Go(root, root);
  vector<bool> was(n);
  was[root] = true;            
  long long f = dp[root];
  auto Rem = [&](int x) {
    while (!was[x]) {
      st.modify(tin[x], tout[x], -up[x]);
      f += up[x];
      was[x] = true;      
      x = par[x];
    }
  };
  for (int i = 2; i <= n; i++) {     
    Rem(ver[st.get(0, n - 1).id]);        
    ans[i] = f;
  }  
  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    cout << total - ans[x] << '\n'; 
  }                                     
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 441 ms 38712 KB Output is correct
3 Correct 447 ms 55360 KB Output is correct
4 Correct 407 ms 37252 KB Output is correct
5 Correct 398 ms 38864 KB Output is correct
6 Correct 448 ms 40904 KB Output is correct
7 Correct 376 ms 38580 KB Output is correct
8 Correct 472 ms 55172 KB Output is correct
9 Correct 368 ms 39180 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 403 ms 38540 KB Output is correct
3 Correct 451 ms 57664 KB Output is correct
4 Correct 426 ms 37244 KB Output is correct
5 Correct 420 ms 38892 KB Output is correct
6 Correct 493 ms 41708 KB Output is correct
7 Correct 316 ms 38932 KB Output is correct
8 Correct 507 ms 49864 KB Output is correct
9 Correct 321 ms 38800 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 328 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 840 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 3 ms 612 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 3 ms 676 KB Output is correct
20 Correct 3 ms 724 KB Output is correct
21 Correct 3 ms 736 KB Output is correct
22 Correct 3 ms 724 KB Output is correct
23 Correct 3 ms 716 KB Output is correct
24 Correct 4 ms 724 KB Output is correct
25 Correct 3 ms 852 KB Output is correct
26 Correct 3 ms 724 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 441 ms 38712 KB Output is correct
3 Correct 447 ms 55360 KB Output is correct
4 Correct 407 ms 37252 KB Output is correct
5 Correct 398 ms 38864 KB Output is correct
6 Correct 448 ms 40904 KB Output is correct
7 Correct 376 ms 38580 KB Output is correct
8 Correct 472 ms 55172 KB Output is correct
9 Correct 368 ms 39180 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 403 ms 38540 KB Output is correct
12 Correct 451 ms 57664 KB Output is correct
13 Correct 426 ms 37244 KB Output is correct
14 Correct 420 ms 38892 KB Output is correct
15 Correct 493 ms 41708 KB Output is correct
16 Correct 316 ms 38932 KB Output is correct
17 Correct 507 ms 49864 KB Output is correct
18 Correct 321 ms 38800 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 424 ms 38736 KB Output is correct
21 Correct 445 ms 57776 KB Output is correct
22 Correct 368 ms 37260 KB Output is correct
23 Correct 463 ms 38684 KB Output is correct
24 Correct 400 ms 37496 KB Output is correct
25 Correct 430 ms 38892 KB Output is correct
26 Correct 444 ms 37484 KB Output is correct
27 Correct 414 ms 38732 KB Output is correct
28 Correct 429 ms 41152 KB Output is correct
29 Correct 431 ms 38636 KB Output is correct
30 Correct 412 ms 38144 KB Output is correct
31 Correct 347 ms 38636 KB Output is correct
32 Correct 495 ms 50408 KB Output is correct
33 Correct 307 ms 39204 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 441 ms 38712 KB Output is correct
14 Correct 447 ms 55360 KB Output is correct
15 Correct 407 ms 37252 KB Output is correct
16 Correct 398 ms 38864 KB Output is correct
17 Correct 448 ms 40904 KB Output is correct
18 Correct 376 ms 38580 KB Output is correct
19 Correct 472 ms 55172 KB Output is correct
20 Correct 368 ms 39180 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 403 ms 38540 KB Output is correct
23 Correct 451 ms 57664 KB Output is correct
24 Correct 426 ms 37244 KB Output is correct
25 Correct 420 ms 38892 KB Output is correct
26 Correct 493 ms 41708 KB Output is correct
27 Correct 316 ms 38932 KB Output is correct
28 Correct 507 ms 49864 KB Output is correct
29 Correct 321 ms 38800 KB Output is correct
30 Correct 0 ms 328 KB Output is correct
31 Correct 3 ms 604 KB Output is correct
32 Correct 3 ms 840 KB Output is correct
33 Correct 3 ms 596 KB Output is correct
34 Correct 3 ms 724 KB Output is correct
35 Correct 3 ms 612 KB Output is correct
36 Correct 3 ms 724 KB Output is correct
37 Correct 3 ms 676 KB Output is correct
38 Correct 3 ms 724 KB Output is correct
39 Correct 3 ms 736 KB Output is correct
40 Correct 3 ms 724 KB Output is correct
41 Correct 3 ms 716 KB Output is correct
42 Correct 4 ms 724 KB Output is correct
43 Correct 3 ms 852 KB Output is correct
44 Correct 3 ms 724 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 424 ms 38736 KB Output is correct
47 Correct 445 ms 57776 KB Output is correct
48 Correct 368 ms 37260 KB Output is correct
49 Correct 463 ms 38684 KB Output is correct
50 Correct 400 ms 37496 KB Output is correct
51 Correct 430 ms 38892 KB Output is correct
52 Correct 444 ms 37484 KB Output is correct
53 Correct 414 ms 38732 KB Output is correct
54 Correct 429 ms 41152 KB Output is correct
55 Correct 431 ms 38636 KB Output is correct
56 Correct 412 ms 38144 KB Output is correct
57 Correct 347 ms 38636 KB Output is correct
58 Correct 495 ms 50408 KB Output is correct
59 Correct 307 ms 39204 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 445 ms 41316 KB Output is correct
62 Correct 444 ms 56964 KB Output is correct
63 Correct 464 ms 39920 KB Output is correct
64 Correct 460 ms 41236 KB Output is correct
65 Correct 418 ms 39824 KB Output is correct
66 Correct 487 ms 41244 KB Output is correct
67 Correct 459 ms 39860 KB Output is correct
68 Correct 464 ms 41444 KB Output is correct
69 Correct 494 ms 43700 KB Output is correct
70 Correct 466 ms 41044 KB Output is correct
71 Correct 420 ms 40960 KB Output is correct
72 Correct 387 ms 41920 KB Output is correct
73 Correct 547 ms 52556 KB Output is correct
74 Correct 378 ms 43388 KB Output is correct