Submission #851035

#	Time	Username	Problem	Language	Result	Execution time	Memory
851035		anhphant	Toll (BOI17_toll)	C++14	100 / 100	1213 ms	399232 KiB

toll

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

using namespace std;

const int N = 50000;
const int inf = 1234567890;
const int C = 2000;
const int Q = 10000;

int dp[N], inQue[N];
int preCompute[C][N];
vector<array<int, 2>> adj[N];
array<int, 2> ques[Q];
int occ[N];

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 < m; i++) {
    int u, v;
    cin >> u >> v;
    int t;
    cin >> t;
    adj[v].push_back({u, t});
  }

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

  vector<int> all;

  for (int i = 0; i < q; i++) {
    cin >> ques[i][0] >> ques[i][1];
    all.push_back(ques[i][0]);
    ++occ[ques[i][0]];
  }

  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());

  sort(all.begin(), all.end(), [&](int i, int j) {
    return occ[i] > occ[j];
  });

  vector<int> pts;
  for (int i = 0; i < min((int) all.size(), C); i++) {
    pts.push_back(all[i]);
    inQue[all[i]] = i;
  }

  for (int i = 0; i < (int) pts.size(); i++) {
    int u = pts[i];
    int b0 = u / k;
    for (int j = b0 * k; j < n; j++) {
      preCompute[i][j] = inf;
    }
    preCompute[i][u] = 0;
    for (int it = (b0 + 1) * k; it < n; it++) {
      for (auto x : adj[it]) {
        preCompute[i][it] = min(preCompute[i][it], preCompute[i][x[0]] + x[1]);
      }
    }
  }

  for (int it = 0; it < q; it++) {
    int u = ques[it][0];
    int v = ques[it][1];
    int b0 = u / k;
    int b1 = v / k;
    if (b0 == b1) {
      cout << -1 << '\n';
    } else {
      int id = inQue[u];
      if (id == -1) {
        dp[u] = 0;
        for (int i = (b0 + 1) * k; i <= v; i++) {
          for (auto x : adj[i]) {
            dp[i] = min(dp[i], dp[x[0]] + x[1]);
          }
        }
        if (dp[v] < inf) {
          cout << dp[v] << '\n';
        } else {
          cout << -1 << '\n';
        }
        dp[u] = inf;
        for (int i = (b0 + 1) * k; i <= v; i++) {
          dp[i] = inf;
        }
      } else {
        if (preCompute[id][v] < inf) {
          cout << preCompute[id][v] << '\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