Submission #1173130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173130		lopkus	Toll (BOI17_toll)	C++20	0 / 100	3093 ms	589824 KiB

toll

#include <bits/stdc++.h>+

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int k, n, m, Q;
  std::cin >> k >> n >> m >> Q;
  std::vector<std::pair<int,int64_t>> adj[n];
  std::vector<int> in(n, 0);
  for(int i = 1; i <= m; i++) {
    int64_t u, v, t;
    std::cin >> u >> v >> t;
    adj[u].push_back({v, t});
    in[v] += 1;
  }
  std::vector<int64_t> dist(n, 1e18);
  std::priority_queue<std::pair<int, int64_t>> pq;
  for(int i = 0; i < n; i++) {
    if(!in[i]) {
      pq.push({0, i});
      dist[i] = 0;
    }
  }
  std::vector<int> was(n);
  while(!pq.empty()) {
    int v = (pq.top()).second;
    pq.pop();
    if(was[v]) {
      continue;
    }
    was[v] = 1;
    for(auto [u, t] : adj[v]) {
      if(dist[u] > dist[v] + t) {
        dist[u] = dist[v] + t;
        pq.push({-dist[u], u});
      }
    }
  }
  while(Q--) {
    int u, v;
    std::cin >> u >> v;
    int ok = 0;
    std::queue<int> q;
    q.push(u);
    std::vector<int> r(n);
    while(!q.empty()) {
      int vv = q.front();
      q.pop();
      if(vv == v) {
        ok = 1;
        break;
      }
      r[vv] = 1;
      for(auto [uu, tt] : adj[vv]) {
        if(!r[uu]) {
          q.push(uu);
        }
      }
    }
    std::cout << (ok ? dist[v] - dist[u] : - 1) << "\n";
  }
}
/**
edge a -> b if a / k + 1 == b / k
does not have cycles
**/

Compilation message (stderr)

toll.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>+
      |                         ^

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