Submission #757784

#	Time	Username	Problem	Language	Result	Execution time	Memory
757784		taher	Toll (BOI17_toll)	C++17	100 / 100	222 ms	49640 KiB

toll

#include <bits/stdc++.h>

using namespace std;

template<typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
  public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<int>& a, const F& f) : func(f) {
    n = (int) a.size();
    mat.resize(n);
    int max_log = 32 - __builtin_clz(n);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= (n - (1 << j)); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) {
    assert(from <= to && from >= 0 && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

const int N = 50000;
const int inf = 1000000000;

int dp[N];
bool inQue[N];
vector<array<int, 2>> adj[N];
vector<array<int, 2>> rAdj[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int k, n, m, q;
  cin >> k >> n >> m >> q;

  int p = (n + k - 1) / k;
  vector<vector<int>> bucket(p);

  for (int i = 0; i < n; i++) {
    bucket[i / k].push_back(i);
  }

  for (int i = 0; i < n; i++) {
    inQue[i] = false;
    dp[i] = inf;
  }

  for (int i = 0; i < m; i++) {
    int u, v, t;
    cin >> u >> v >> t;
    adj[u].push_back({v, t});
    rAdj[v].push_back({u, t});
  }

  vector<vector<vector<vector<pair<int, int>>>>> pts(p * 2, vector<vector<vector<pair<int, int>>>> (k, vector<vector<pair<int, int>>> (2)));

  auto Solve = [&](int midPoint, int cnt) {
    for (int each = 0; each < (int) bucket[midPoint].size(); each++) {
      int x = bucket[midPoint][each];
      dp[x] = 0;
      pts[cnt][each][0].emplace_back(x, 0);
      pts[cnt][each][1].emplace_back(x, 0);
      for (int it = x - 1; it >= 0; it--) {
        if (inQue[it / k]) {
          break;
        }
        for (auto y : adj[it]) {
          dp[it] = min(dp[it], dp[y[0]] + y[1]);
        }
        pts[cnt][each][0].emplace_back(it, dp[it]);
      }
      reverse(pts[cnt][each][0].begin(), pts[cnt][each][0].end());
      for (int it = x - 1; it >= 0; it--) {
        if (inQue[it / k]) {
          break;
        }
        dp[it] = inf;
      }
      for (int it = x + 1; it < n; it++) {
        if (inQue[it / k]) {
          break;
        }
        for (auto y : rAdj[it]) {
          dp[it] = min(dp[it], dp[y[0]] + y[1]);
        }
        pts[cnt][each][1].emplace_back(it, dp[it]);
      }
      for (int it = x; it < n; it++) {
        if (inQue[it / k]) {
          break;
        }
        dp[it] = inf;
      }
    }
  };

  vector<int> at(p, inf);

  auto Divide = [&]() {
    int cnt = 0;
    queue<array<int, 2>> que;
    que.push({0, p - 1});
    while (!que.empty()) {
      auto t = que.front();
      que.pop();
      int low = t[0];
      int high = t[1];
      if (low >= high) {
        continue;
      }
      int midPoint = low + (high - low) / 2;
      Solve(midPoint, cnt);
      inQue[midPoint] = true;
      at[midPoint] = cnt;
      cnt++;
      que.push({low, midPoint});
      que.push({midPoint + 1, high});
    }
  };

  Divide();

  SparseTable<int> st(at, [&](int i, int j) {
    return min(i, j);
  });

  while (q--) {
    int u, v;
    cin >> u >> v;
    int b0 = u / k;
    int b1 = v / k;
    if (b0 == b1) {
      cout << -1 << '\n';
    } else {
      int ans = inf;
      int cnt = st.get(b0, b1);
      for (int each = 0; each < k; each++) {
        if (pts[cnt][each][0].empty()) {
          break;
        }
        int it0 = lower_bound(pts[cnt][each][0].begin(), pts[cnt][each][0].end(), make_pair(u, -inf)) - pts[cnt][each][0].begin();
        int it1 = lower_bound(pts[cnt][each][1].begin(), pts[cnt][each][1].end(), make_pair(v, -inf)) - pts[cnt][each][1].begin();
        if (it0 < (int) pts[cnt][each][0].size() && it1 < (int) pts[cnt][each][1].size()) {
          if (pts[cnt][each][0][it0].first == u && pts[cnt][each][1][it1].first == v) {
            ans = min(ans, pts[cnt][each][0][it0].second + pts[cnt][each][1][it1].second);
          }
        }
      }
      if (ans < inf) {
        cout << ans << '\n';
      } else {
        cout << -1 << '\n';
      }
    }
  }
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44