oj.uz

Submission #284318

# Submission time Handle Problem Language Result Execution time Memory
284318 2020-08-27T08:32:55 Z AlexLuchianov Toll (BOI17_toll) C++14
7 / 100
 85 ms 25848 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const sigma = 5;
int const inf = 1000000000;

struct Matrix {
  int dp[sigma][sigma];
  Matrix() {
    for(int i = 0; i < sigma; i++)
      for(int j = 0; j < sigma; j++)
        dp[i][j] = inf;
  }
  Matrix operator * (Matrix a) {
    Matrix result;
    for(int i = 0; i < sigma; i++)
      for(int j = 0; j < sigma; j++)
        for(int h = 0; h < sigma; h++) 
          result.dp[i][j] = std::min(result.dp[i][j], dp[i][h] + a.dp[h][j]);
    return result;
  }
};

class SegmentTree{
private:
  std::vector<Matrix> aint;
public:
  SegmentTree(int n) {
    aint.resize(1 + 4 * n);
  }
  void build(int node, int from, int to, std::vector<Matrix> &aux) {
    if(from < to) {
      int mid = (from + to) / 2;
      build(node * 2, from, mid, aux);
      build(node * 2 + 1, mid + 1, to, aux);
      aint[node] = aint[node * 2] * aint[node * 2 + 1];
    } else
      aint[node] = aux[from];
  }
  Matrix query(int node, int from, int to, int x, int y) {
    if(from == x && to == y)
      return aint[node];
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y);
      else
        return query(node *2 , from, mid, x, mid) * query(node * 2 +1 , mid + 1, to, mid + 1, y);
    }
  }
};

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int k, n, m, q;
  std::cin >> k >> n >> m >> q;
  
  std::vector<Matrix> aux(n / k);
  for(int i = 1;i <= m; i++) {
    int x, y, cost;
    std::cin >> x >> y >> cost;
    aux[x / k].dp[x % k][y % k] = cost;
  }
  SegmentTree aint(n);
  aint.build(1, 0, n / k - 1, aux);
  for(int i = 1;i <= q; i++) {
    int x, y;
    std::cin >> x >> y;
    if(x / k == y / k)
      std::cout << -1;
    else {
      Matrix ext = aint.query(1, 0, n / k - 1, x/ k, y / k - 1);
      int result = ext.dp[x % k][y % k];
      if(result == inf)
        std::cout << -1 << '\n';
      else
        std::cout << result << '\n';
       
    }
  }
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 25848 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 80 ms 25796 KB Output is correct
9 Correct 85 ms 25772 KB Output is correct
10 Correct 66 ms 24952 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 24100 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 25848 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 80 ms 25796 KB Output is correct
9 Correct 85 ms 25772 KB Output is correct
10 Correct 66 ms 24952 KB Output is correct
11 Correct 81 ms 24100 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Incorrect 0 ms 384 KB Output isn't correct
14 Halted 0 ms 0 KB -