제출 #1096193

#제출 시각아이디문제언어결과실행 시간메모리
1096193anarch_yToll (BOI17_toll)C++17
100 / 100
185 ms89276 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define pb push_back int main(){ ios::sync_with_stdio(0); cin.tie(0); using Matrix = array<array<int, 5>, 5>; Matrix id; for(int i=0; i<5; i++){ for(int j=0; j<5; j++){ if(i != j) id[i][j] = 1e9; else id[i][j] = 0; } } auto mult = [&](Matrix A, Matrix B){ Matrix C; for(int i=0; i<5; i++){ for(int j=0; j<5; j++){ C[i][j] = 1e9; for(int k=0; k<5; k++){ C[i][j] = min(C[i][j], A[i][k] + B[k][j]); } } } return C; }; int k, n, m, q; cin >> k >> n >> m >> q; n = (n-1)/k; Matrix to[n][18]; for(int j=0; j<=17; j++){ for(int i=0; i<n; i++){ for(int x=0; x<5; x++){ for(int y=0; y<5; y++) to[i][j][x][y] = 1e9; } } } while(m--){ int a, b, t; cin >> a >> b >> t; int c = a/k, d = b/k; to[c][0][a-k*c][b-k*d] = t; } for(int j=1; j<=17; j++){ for(int i=0; i+(1<<j)<=n; i++){ to[i][j] = mult(to[i][j-1], to[i+(1<<(j-1))][j-1]); } } while(q--){ int a, b; cin >> a >> b; int c = a/k, d = b/k; if(c >= d){ cout << -1 << "\n"; continue; } int y = d-c; Matrix C = id; for(int j=17; j>=0; j--){ if(y & (1<<j)){ C = mult(C, to[c][j]); c = c+(1<<j); } } c = a/k; int ans = C[a-k*c][b-k*d]; if(ans == 1e9) ans = -1; cout << ans << "\n"; } }
#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...