# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
529941 | 2022-02-24T06:10:35 Z | 79brue | Toll (BOI17_toll) | C++14 | 172 ms | 160672 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; int k, n, m, q; int sps[50002][5][5][16]; int main(){ scanf("%d %d %d %d", &k, &n, &m, &q); for(int i=0; i<=n; i++) for(int j=0; j<5; j++) for(int x=0; x<5; x++) for(int y=0; y<16; y++) sps[i][j][x][y] = 1e9; while(m--){ int a, b, v; scanf("%d %d %d", &a, &b, &v); sps[a/k][a%k][b%k][0] = min(sps[a/k][a%k][b%k][0], v); } for(int d=0; d<16; d++){ for(int i=0; i<=n/k; i++){ for(int x=0; x<k; x++) for(int y=0; y<k; y++) for(int z=0; z<k; z++){ sps[i][x][z][d+1] = min(sps[i][x][z][d+1], sps[i][x][y][d] + sps[i+(1<<d)][y][z][d]); } } } while(q--){ int S, E; scanf("%d %d", &S, &E); if(S/k >= E/k){ puts("0"); continue; } vector<int> dist (k, 1e9); dist[S%k] = 0; int sg = S/k, eg = E/k, gd = eg - sg; for(int d=0; d<16; d++){ if((gd >> d) & 1){ vector<int> dist2 (k, 1e9); for(int i=0; i<k; i++){ for(int j=0; j<k; j++){ dist2[j] = min(dist2[j], dist[i] + sps[sg][i][j][d]); } } sg += 1<<d; dist = dist2; } } printf("%d\n", dist[E%k]>=1e9 ? -1 : dist[E%k]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 127 ms | 159932 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 172 ms | 160672 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 284 KB | Output is correct |
2 | Incorrect | 1 ms | 304 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 284 KB | Output is correct |
2 | Incorrect | 1 ms | 304 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 127 ms | 159932 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |