oj.uz

Submission #600404

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

using namespace std;

const int N = 100005;
const int inf = 1e8;

int d[N][5][5];

class segtree {
  public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    int 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 {
      int ans = st.get(a / k, b / k).dist[a % k][b % k];
      cout << (ans == inf ? -1 : ans) << '\n';
    }
  }                                   
  return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 350 ms 20680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 15428 KB Output is correct
2 Correct 5 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 6 ms 9988 KB Output is correct
5 Correct 5 ms 9992 KB Output is correct
6 Correct 6 ms 10104 KB Output is correct
7 Correct 103 ms 10408 KB Output is correct
8 Correct 84 ms 10312 KB Output is correct
9 Correct 220 ms 21568 KB Output is correct
10 Correct 188 ms 15936 KB Output is correct
11 Correct 195 ms 17072 KB Output is correct
12 Correct 171 ms 14816 KB Output is correct
13 Correct 102 ms 13788 KB Output is correct
14 Correct 72 ms 13688 KB Output is correct
15 Correct 61 ms 12524 KB Output is correct
16 Correct 62 ms 12512 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10068 KB Output is correct
2 Correct 5 ms 10068 KB Output is correct
3 Correct 6 ms 10068 KB Output is correct
4 Correct 5 ms 10068 KB Output is correct
5 Correct 5 ms 10068 KB Output is correct
6 Correct 8 ms 10324 KB Output is correct
7 Correct 10 ms 10196 KB Output is correct
8 Correct 9 ms 10196 KB Output is correct
9 Correct 7 ms 10140 KB Output is correct
10 Correct 62 ms 21452 KB Output is correct
11 Correct 53 ms 16908 KB Output is correct
12 Correct 53 ms 15812 KB Output is correct
13 Correct 63 ms 15960 KB Output is correct
14 Correct 56 ms 15436 KB Output is correct
15 Correct 34 ms 12516 KB Output is correct
16 Correct 39 ms 12492 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10068 KB Output is correct
2 Correct 5 ms 10068 KB Output is correct
3 Correct 6 ms 10068 KB Output is correct
4 Correct 5 ms 10068 KB Output is correct
5 Correct 5 ms 10068 KB Output is correct
6 Correct 8 ms 10324 KB Output is correct
7 Correct 10 ms 10196 KB Output is correct
8 Correct 9 ms 10196 KB Output is correct
9 Correct 7 ms 10140 KB Output is correct
10 Correct 62 ms 21452 KB Output is correct
11 Correct 53 ms 16908 KB Output is correct
12 Correct 53 ms 15812 KB Output is correct
13 Correct 63 ms 15960 KB Output is correct
14 Correct 56 ms 15436 KB Output is correct
15 Correct 34 ms 12516 KB Output is correct
16 Correct 39 ms 12492 KB Output is correct
17 Correct 121 ms 16980 KB Output is correct
18 Correct 5 ms 10060 KB Output is correct
19 Correct 5 ms 10068 KB Output is correct
20 Correct 6 ms 10056 KB Output is correct
21 Correct 6 ms 10068 KB Output is correct
22 Correct 6 ms 10068 KB Output is correct
23 Correct 56 ms 10372 KB Output is correct
24 Correct 52 ms 10264 KB Output is correct
25 Correct 42 ms 10232 KB Output is correct
26 Correct 42 ms 10240 KB Output is correct
27 Correct 158 ms 21512 KB Output is correct
28 Correct 132 ms 15836 KB Output is correct
29 Correct 131 ms 16076 KB Output is correct
30 Correct 130 ms 15472 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 350 ms 20680 KB Output isn't correct
2 Halted 0 ms 0 KB -