Submission #284318

#	Time	Username	Problem	Language	Result	Execution time	Memory
284318		AlexLuchianov	Toll (BOI17_toll)	C++14	7 / 100	85 ms	25848 KiB

toll

#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 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44