oj.uz

Submission #600405

# Submission time Handle Problem Language Result Execution time Memory
600405 2022-07-20T20:16:05 Z MilosMilutinovic Toll (BOI17_toll) C++14
100 / 100
 376 ms 41296 KB 
/**
 *    author:  wxhtzdy
 *    created: 20.07.2022 21:48:11
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const long long inf = 1e15;

long long d[N][5][5];

class segtree {
  public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    long long dist[5][5];
    int L;
    int R;         
    void apply(int l, int r, int v) {
      L = v;
      R = v;
      for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
          dist[i][j] = (i == j ? 0 : inf);
        }
      }
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    res.L = a.L;
    res.R = b.R;
    for (int i = 0; i < 5; i++) {
      for (int j = 0; j < 5; j++) {
        res.dist[i][j] = inf;
      }
    }
    for (int i1 = 0; i1 < 5; i1++) {
      for (int i2 = 0; i2 < 5; i2++) {
        for (int i3 = 0; i3 < 5; i3++) {
          for (int i4 = 0; i4 < 5; i4++) {
            res.dist[i1][i4] = min(res.dist[i1][i4], a.dist[i1][i2] + d[a.R][i2][i3] + b.dist[i3][i4]);
          }
        }
      }
    }
    return res;
  }
  inline void push(int x, int l, int r) {
  }
  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) {
    if (l == r) {  
      tree[x].apply(l, l, l);
      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 k, n, m, q;
  cin >> k >> n >> m >> q;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 5; j++) {
      for (int l = 0; l < 5; l++) {
        d[i][j][l] = inf;
      }
    }
  }
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    d[x / k][x % k][y % k] = z;
  }        
  n = (n + k - 1) / k;
  segtree st(n);
  while (q--) {
    int a, b;
    cin >> a >> b;
    if (a / k >= b / k) {
      cout << -1 << '\n';
    } else {
      long long ans = st.get(a / k, b / k).dist[a % k][b % k];
      cout << (ans == inf ? -1 : ans) << '\n';
    }
  }                                   
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 40428 KB Output is correct
2 Correct 8 ms 19796 KB Output is correct
3 Correct 8 ms 19796 KB Output is correct
4 Correct 10 ms 19868 KB Output is correct
5 Correct 28 ms 20236 KB Output is correct
6 Correct 32 ms 20332 KB Output is correct
7 Correct 26 ms 20332 KB Output is correct
8 Correct 372 ms 41296 KB Output is correct
9 Correct 376 ms 41228 KB Output is correct
10 Correct 362 ms 40428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 30172 KB Output is correct
2 Correct 8 ms 19768 KB Output is correct
3 Correct 10 ms 19792 KB Output is correct
4 Correct 9 ms 19776 KB Output is correct
5 Correct 9 ms 19788 KB Output is correct
6 Correct 10 ms 19796 KB Output is correct
7 Correct 104 ms 20312 KB Output is correct
8 Correct 98 ms 20128 KB Output is correct
9 Correct 222 ms 40268 KB Output is correct
10 Correct 196 ms 26704 KB Output is correct
11 Correct 213 ms 30076 KB Output is correct
12 Correct 179 ms 26668 KB Output is correct
13 Correct 83 ms 22348 KB Output is correct
14 Correct 75 ms 23980 KB Output is correct
15 Correct 64 ms 22344 KB Output is correct
16 Correct 72 ms 22336 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19796 KB Output is correct
2 Correct 12 ms 19792 KB Output is correct
3 Correct 9 ms 19852 KB Output is correct
4 Correct 9 ms 19796 KB Output is correct
5 Correct 9 ms 19796 KB Output is correct
6 Correct 13 ms 20308 KB Output is correct
7 Correct 11 ms 20052 KB Output is correct
8 Correct 11 ms 19868 KB Output is correct
9 Correct 11 ms 19924 KB Output is correct
10 Correct 72 ms 40240 KB Output is correct
11 Correct 67 ms 30064 KB Output is correct
12 Correct 70 ms 26664 KB Output is correct
13 Correct 83 ms 26584 KB Output is correct
14 Correct 52 ms 26664 KB Output is correct
15 Correct 32 ms 22320 KB Output is correct
16 Correct 31 ms 22356 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19796 KB Output is correct
2 Correct 12 ms 19792 KB Output is correct
3 Correct 9 ms 19852 KB Output is correct
4 Correct 9 ms 19796 KB Output is correct
5 Correct 9 ms 19796 KB Output is correct
6 Correct 13 ms 20308 KB Output is correct
7 Correct 11 ms 20052 KB Output is correct
8 Correct 11 ms 19868 KB Output is correct
9 Correct 11 ms 19924 KB Output is correct
10 Correct 72 ms 40240 KB Output is correct
11 Correct 67 ms 30064 KB Output is correct
12 Correct 70 ms 26664 KB Output is correct
13 Correct 83 ms 26584 KB Output is correct
14 Correct 52 ms 26664 KB Output is correct
15 Correct 32 ms 22320 KB Output is correct
16 Correct 31 ms 22356 KB Output is correct
17 Correct 137 ms 30104 KB Output is correct
18 Correct 9 ms 19796 KB Output is correct
19 Correct 11 ms 19796 KB Output is correct
20 Correct 10 ms 19796 KB Output is correct
21 Correct 9 ms 19796 KB Output is correct
22 Correct 9 ms 19796 KB Output is correct
23 Correct 58 ms 20268 KB Output is correct
24 Correct 51 ms 20112 KB Output is correct
25 Correct 44 ms 19988 KB Output is correct
26 Correct 45 ms 19980 KB Output is correct
27 Correct 167 ms 40240 KB Output is correct
28 Correct 178 ms 26672 KB Output is correct
29 Correct 135 ms 26652 KB Output is correct
30 Correct 126 ms 26656 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 40428 KB Output is correct
2 Correct 8 ms 19796 KB Output is correct
3 Correct 8 ms 19796 KB Output is correct
4 Correct 10 ms 19868 KB Output is correct
5 Correct 28 ms 20236 KB Output is correct
6 Correct 32 ms 20332 KB Output is correct
7 Correct 26 ms 20332 KB Output is correct
8 Correct 372 ms 41296 KB Output is correct
9 Correct 376 ms 41228 KB Output is correct
10 Correct 362 ms 40428 KB Output is correct
11 Correct 220 ms 30172 KB Output is correct
12 Correct 8 ms 19768 KB Output is correct
13 Correct 10 ms 19792 KB Output is correct
14 Correct 9 ms 19776 KB Output is correct
15 Correct 9 ms 19788 KB Output is correct
16 Correct 10 ms 19796 KB Output is correct
17 Correct 104 ms 20312 KB Output is correct
18 Correct 98 ms 20128 KB Output is correct
19 Correct 222 ms 40268 KB Output is correct
20 Correct 196 ms 26704 KB Output is correct
21 Correct 213 ms 30076 KB Output is correct
22 Correct 179 ms 26668 KB Output is correct
23 Correct 83 ms 22348 KB Output is correct
24 Correct 75 ms 23980 KB Output is correct
25 Correct 64 ms 22344 KB Output is correct
26 Correct 72 ms 22336 KB Output is correct
27 Correct 9 ms 19796 KB Output is correct
28 Correct 12 ms 19792 KB Output is correct
29 Correct 9 ms 19852 KB Output is correct
30 Correct 9 ms 19796 KB Output is correct
31 Correct 9 ms 19796 KB Output is correct
32 Correct 13 ms 20308 KB Output is correct
33 Correct 11 ms 20052 KB Output is correct
34 Correct 11 ms 19868 KB Output is correct
35 Correct 11 ms 19924 KB Output is correct
36 Correct 72 ms 40240 KB Output is correct
37 Correct 67 ms 30064 KB Output is correct
38 Correct 70 ms 26664 KB Output is correct
39 Correct 83 ms 26584 KB Output is correct
40 Correct 52 ms 26664 KB Output is correct
41 Correct 32 ms 22320 KB Output is correct
42 Correct 31 ms 22356 KB Output is correct
43 Correct 137 ms 30104 KB Output is correct
44 Correct 9 ms 19796 KB Output is correct
45 Correct 11 ms 19796 KB Output is correct
46 Correct 10 ms 19796 KB Output is correct
47 Correct 9 ms 19796 KB Output is correct
48 Correct 9 ms 19796 KB Output is correct
49 Correct 58 ms 20268 KB Output is correct
50 Correct 51 ms 20112 KB Output is correct
51 Correct 44 ms 19988 KB Output is correct
52 Correct 45 ms 19980 KB Output is correct
53 Correct 167 ms 40240 KB Output is correct
54 Correct 178 ms 26672 KB Output is correct
55 Correct 135 ms 26652 KB Output is correct
56 Correct 126 ms 26656 KB Output is correct
57 Correct 367 ms 28360 KB Output is correct
58 Correct 361 ms 41180 KB Output is correct
59 Correct 369 ms 31888 KB Output is correct