Submission #1263590

#TimeUsernameProblemLanguageResultExecution timeMemory
1263590shiori_chanToll (BOI17_toll)C++17
100 / 100
101 ms63668 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ii pair<int, int> const int N = 1e6 + 5; int upf[N][18][5]; int d[N]; vector<ii> a[N]; bool vis[N]; int k, n, m, o; void bfs() { for (int u = n; u >= 0; u--) { for (auto P : a[u]) { upf[u][0][P.first % k] = min(upf[u][0][P.first % k], P.second); } for (int g = 1; g < 16; g++) { for (int j = 0; j < k; j++) { for (int p = 0; p < k; p++) { int nodep = (u / k + (1 << (g-1))) * k + p; upf[u][g][j] = min(upf[u][g][j], upf[u][g-1][p] + upf[nodep][g-1][j]); } } } } } inline int jump(pair<int, int> x, pair<int, int> y) { int z = y.first - x.first; int currb[5] = {(int)1e16, (int)1e16, (int)1e16, (int)1e16, (int)1e16}; currb[x.second] = 0; int floor = x.first; for (int j = 0; (1 << j) <= z; j++) { if ((z >> j) & 1) { int curr[5] = {(int)1e16, (int)1e16, (int)1e16, (int)1e16, (int)1e16}; for (int p = 0; p < k; p++) { for (int y = 0; y < k; y++) { curr[p] = min(curr[p], currb[y] + upf[floor*k+y][j][p]); } } floor += (1 << j); swap(curr, currb); } } return currb[y.second]; } int query(int u, int v) { int x = jump({u / k, u % k}, {v / k, v % k}); return x; } signed main() { if (fopen("D.inp", "r")) { freopen("D.inp", "r", stdin); freopen("D.out", "w", stdout); } cin.tie(0)->sync_with_stdio(false); cin >> k >> n >> m >> o; for (int i = 0; i <= n; i++) { for (int j = 0; j < 20; j++) { for (int x = 0; x < k; x++) { upf[i][j][x] = 1e16; // up[i][j][x] = -1; } } } for (int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; a[u].push_back({v, w}); } bfs(); while (o--) { int u, v; cin >> u >> v; if (u / k > v/k || (u / k == v / k && u != v)) { cout << "-1\n"; continue; } int x = query(u, v); if (x >= 1e16) cout << "-1\n"; else cout << x << '\n'; } return 0; }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("D.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("D.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...