Submission #915806

#TimeUsernameProblemLanguageResultExecution timeMemory
915806asdasdqwerToll (BOI17_toll)C++14
100 / 100
362 ms69556 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t const int INF = 1e14; signed main() { int k,n,m,o;cin>>k>>n>>m>>o; int cl=(n/k)+1; vector<vector<vector<vector<int>>>> lft(cl, vector<vector<vector<int>>>(k, vector<vector<int>>(18, vector<int>(k, INF)))); for (int i=0;i<m;i++) { int a,b,t;cin>>a>>b>>t; lft[a/k][a%k][0][b%k]=t; } for (int j=1;j<18;j++) { for (int i=0;i<cl;i++) { if (i + (1<<j) >= cl)break; for (int t=0;t<k;t++) { for (int md=0;md<k;md++) { for (int tr=0;tr<k;tr++) { lft[i][t][j][tr] = min(lft[i][t][j][tr], lft[i][t][j-1][md] + lft[i+(1<<(j-1))][md][j-1][tr]); } } } } } while (o--) { int a,b;cin>>a>>b; if ((a/k) == (b/k)) { cout<<"-1\n"; continue; } int rw = a/k, co=a%k; int steps = (b/k) - (a/k); vector<int> jmp(k); for (int i=0;i<k;i++) { jmp[i] = lft[rw][co][0][i]; } steps--; rw++; int cnt=0; while (steps) { if ((steps&1)==1) { vector<int> tmpjmp(k, INF); for (int i=0;i<k;i++) { // use i as a starting point for (int j=0;j<k;j++) { // use j as an ending point tmpjmp[j] = min(tmpjmp[j], jmp[i] + lft[rw][i][cnt][j]); } } jmp = tmpjmp; rw+=(1<<cnt); } steps>>=1; cnt++; } if (jmp[b%k] >= INF) { cout<<-1<<"\n"; continue; } cout<<jmp[b%k]<<"\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...