# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244634 | 2020-07-04T13:14:15 Z | TheLorax | Toll (BOI17_toll) | C++11 | 87 ms | 12156 KB |
#include <bits/stdc++.h> //#pragma GCC optimize ("O3") //#pragma GCC optimize ("Ofast") #define F first #define S second #define MT make_tuple #define MP make_pair #define SZ(a) ((int)(a).size()) #define PB push_back #define LEFT(i) (2*(i)) #define RIGHT(i) (2*(i)+1) #define PAR(i) ((i)/2) #define ALL(a) (a).begin(), (a).end() #define END(s) {cout << s;return;} using namespace std; typedef long long ll; typedef pair<ll, ll> ii; int main(){ int k, n, m, o; scanf("%d %d %d %d", &k,&n,&m,&o); n=k*(n/k+1); int lgn=0; while ((1<<lgn)*k<n) lgn++; ll dis[n][k][lgn]; for(int i=0; i<n; i++) for(int j=0; j<k; j++) for(int l=0; l<lgn; l++) dis[i][j][l]=INT_MAX*10LL; for(int i=0; i<m; i++){ int a, b, t; scanf("%d %d %d", &a, &b, &t); dis[a][b%5][0]=t; } for(int l=1; l<lgn; l++) for(int i=0; i<n; i++) for(int j=0; j<k; j++) for(int p=0; p<k; p++) if(p+k*(i/k+(1<<(l-1)))<n) dis[i][j][l]=min(dis[i][j][l], dis[i][p][l-1]+dis[p+k*(i/k+(1<<(l-1)))][j][l-1]); for(int q=0; q<o; q++){ int a, b; scanf("%d %d", &a, &b); int d=b/k-a/k; std::vector<ll> t(k, INT_MAX*10LL), t2(k,INT_MAX*10LL); t2[a%k]=0; a-=a%k; for(int i=20; i>=0; i--){ if(!((1<<i)&d)) continue; for(int j=0; j<k; j++) for(int p=0; p<k; p++) t[j]=min(t[j], t2[p]+dis[p+a][j][i]); a+=(1<<i)*k; for(int j=0; j<k; j++){ t2[j]=t[j]; t[j]=INT_MAX*10LL; } } if(t2[b%k]>INT_MAX) t2[b%k]=-1; printf("%lld\n", t2[b%k]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 44 ms | 6656 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 87 ms | 12156 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 256 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 256 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 44 ms | 6656 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |