Submission #244698

#TimeUsernameProblemLanguageResultExecution timeMemory
244698santaclaus03Toll (BOI17_toll)C++14
7 / 100
355 ms50040 KiB
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; using vvii = vector<vector<ii>>; using vvi = vector<vi>; using vvvi = vector<vvi>; #define INF 1000000000 int main() { int K, n, m, o; cin >> K >> n >> m >> o; vvii rev(n); for (int i = 0; i < m; ++i) { int a, b, t; cin >> a >> b >> t; rev[b].emplace_back(t, a); } int S = (int) round(sqrt(n)); int G = (int) ceil((double) n / S); vvvi dist(G, vvi(S + K, vi(S + K, INF))); for (int g = 0; g < G; ++g) { for (int u = 0; u < S + K; ++u) { dist[g][u][u] = 0; for (int v = u + 1; v < S + K; ++v) { if (u + g * S >= n || v + g * S >= n) continue; for (ii e : rev[v + g * S]) { int w = e.second - g * S; if (w < u) continue; dist[g][u][v] = min(dist[g][u][v], dist[g][u][w] + e.first); } } } } for (int i = 0; i < o; ++i) { int a, b; cin >> a >> b; if (b < a) { cout << -1 << endl; continue; } int ans = INF; int g1 = a / S, g2 = b / S; if (g1 == g2) { ans = dist[g1][a % S][b % S]; } else { vvi d(G, vi(K, INF)); for (int k = 0; k < K; ++k) { d.at(g1+1).at(k) = dist[g1][a % S][k + S]; } for (int g = g1 + 2; g <= g2; ++g) { for (int k1 = 0; k1 < K; ++k1) { for (int k2 = 0; k2 < K; ++k2) { d[g][k1] = min(d.at(g).at(k1), d.at(g-1).at(k2) + dist.at(g-1).at(k2).at(k1 + S)); } } } for (int k = 0; k < K; ++k) { ans = min(ans, d.at(g2).at(k) + dist[g2][k][b % S]); } } cout << (ans == INF ? -1 : ans) << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...