oj.uz

Submission #1047226

# Submission time Handle Problem Language Result Execution time Memory
1047226 2024-08-07T11:05:09 Z avighna Toll (BOI17_toll) C++17
7 / 100
 44 ms 33116 KB 
#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;
const ll N = 50001;
const ll K = 5;

ll adj[N][K];

ll k;

struct Node {
  std::vector<std::vector<ll>> arr;
  ll tl = -1, tr = -1;

  Node() {}
};

bool operator==(const Node &a, const Node &b) { return a.arr == b.arr; }

class SegmentTree {
public:
  std::vector<Node> seg;
  ll n;

  SegmentTree(ll n) {
    this->n = n;
    seg.resize(4 * n);
  }

  Node idt() { return Node(); }
  Node f(const Node &a, const Node &b) {
    if (a == idt()) {
      return b;
    }
    if (b == idt()) {
      return a;
    }

    Node ret;
    ret.tl = a.tl, ret.tr = b.tr;
    auto &ans = ret.arr;
    ans = std::vector<std::vector<ll>>(k, std::vector<ll>(k, inf));
    for (ll s = 0; s < k; ++s) {
      for (ll e = 0; e < k; ++e) {
        for (ll s1 = 0; s1 < k; ++s1) {
          for (ll e1 = 0; e1 < k; ++e1) {
            ans[s][e] =
                std::min(ans[s][e],
                         a.arr[s][s1] + adj[k * a.tr + s1][e1] + b.arr[e1][e]);
          }
        }
      }
    }
    return ret;
  }

  void construct(ll v, ll tl, ll tr) {
    if (tl == tr) {
      seg[v] = Node();
      seg[v].tl = tl, seg[v].tr = tr;
      seg[v].arr = std::vector<std::vector<ll>>(k, std::vector<ll>(k, inf));
      for (ll i = 0; i < k; ++i) {
        seg[v].arr[i][i] = 0;
      }
    } else {
      ll tm = (tl + tr) / 2;
      construct(2 * v, tl, tm);
      construct(2 * v + 1, tm + 1, tr);
      seg[v] = f(seg[2 * v], seg[2 * v + 1]);
    }
  }
  void construct() { construct(1, 0, n); }

  Node query(ll v, ll tl, ll tr, ll l, ll r) {
    if (tl > tr || l > r || tr < l || r < tl) {
      return idt();
    }
    if (l <= tl && tr <= r) {
      return seg[v];
    }
    ll tm = (tl + tr) / 2;
    return f(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
  }
  Node query(ll l, ll r) { return query(1, 0, n, l, r); }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, m, o;
  std::cin >> k >> n >> m >> o;

  for (ll i = 0; i < n; ++i) {
    for (ll j = 0; j < k; ++j) {
      adj[i][j] = inf;
    }
  }
  for (ll i = 0, a, b, t; i < m; ++i) {
    std::cin >> a >> b >> t;
    adj[a][b - a - (k - (a % k))] = t;
  }

  SegmentTree tree(n);
  tree.construct();
  while (o--) {
    ll a, b;
    std::cin >> a >> b;
    auto q = tree.query(a / k, b / k);
    ll ans = q.arr[a % k][b % k];
    std::cout << (ans == inf ? -1 : ans) << '\n';
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16472 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 38 ms 16528 KB Output is correct
9 Correct 38 ms 16456 KB Output is correct
10 Correct 44 ms 16476 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 33104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 2 ms 1120 KB Output is correct
10 Correct 16 ms 16388 KB Output is correct
11 Runtime error 28 ms 33116 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 2 ms 1120 KB Output is correct
10 Correct 16 ms 16388 KB Output is correct
11 Runtime error 28 ms 33116 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16472 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 38 ms 16528 KB Output is correct
9 Correct 38 ms 16456 KB Output is correct
10 Correct 44 ms 16476 KB Output is correct
11 Runtime error 28 ms 33104 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -