oj.uz

Submission #912286

# Submission time Handle Problem Language Result Execution time Memory
912286 2024-01-19T09:36:51 Z imarn Toll (BOI17_toll) C++14
7 / 100
 278 ms 166992 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
using namespace std;
ll dp[50001][17][5][5];
void pre(int i,int j,int ii,int jj,int iii,int jjj){
    for(int x=0;x<5;x++){
        for(int y=0;y<5;y++){
            for(int z=0;z<5;z++){
                dp[i][j][x][y]=min(dp[i][j][x][y],dp[ii][jj][x][z]+dp[iii][jjj][z][y]);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int k,n,m,o;cin>>k>>n>>m>>o;
    for(int i=0;i<50001;i++)for(int j=0;j<17;j++)for(int t=0;t<5;t++)for(int l=0;l<5;l++)dp[i][j][t][l]=1e15;
    while(m--){
        int a,b,t;cin>>a>>b>>t;
        dp[a/k][0][a%k][b%k]=t;
    }
    for(int j=1;j<17;j++){
        for(int i=0;i<(n-k+1)/k;i++){
            if(i+(1<<(j-1))<50001)pre(i,j,i,j-1,i+(1<<(j-1)),j-1);
        }
    }ll ans[5]={0},tmp[5]={0};
    while(o--){
        int a,b;cin>>a>>b;
        if(a==b){
            cout<<0<<'\n';continue;
        }
        for(int i=0;i<5;i++)ans[i]=dp[a/k][0][a%k][i];
        int cur=a/k,dest=b/k;cur++;
        for(int i=16;i>=0;i--){
            if(cur+(1<<i)<=dest){
                for(int x=0;x<k;x++)tmp[x]=1e15;
                for(int y=0;y<k;y++){
                    for(int z=0;z<k;z++){
                        tmp[y]=min(tmp[y],ans[z]+dp[cur][i][z][y]);
                    }
                }for(int x=0;x<k;x++)ans[x]=tmp[x];
                cur+=(1<<i);
            }
        }cout<<(ans[b%k]==1e15?-1:ans[b%k])<<'\n';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 166748 KB Output is correct
2 Correct 29 ms 166740 KB Output is correct
3 Correct 29 ms 166696 KB Output is correct
4 Correct 29 ms 166736 KB Output is correct
5 Correct 32 ms 166700 KB Output is correct
6 Correct 33 ms 166736 KB Output is correct
7 Correct 32 ms 166740 KB Output is correct
8 Correct 276 ms 166740 KB Output is correct
9 Correct 267 ms 166992 KB Output is correct
10 Correct 256 ms 166776 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 166744 KB Output is correct
2 Correct 30 ms 166632 KB Output is correct
3 Incorrect 30 ms 166544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 166560 KB Output is correct
2 Incorrect 30 ms 166736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 166560 KB Output is correct
2 Incorrect 30 ms 166736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 166748 KB Output is correct
2 Correct 29 ms 166740 KB Output is correct
3 Correct 29 ms 166696 KB Output is correct
4 Correct 29 ms 166736 KB Output is correct
5 Correct 32 ms 166700 KB Output is correct
6 Correct 33 ms 166736 KB Output is correct
7 Correct 32 ms 166740 KB Output is correct
8 Correct 276 ms 166740 KB Output is correct
9 Correct 267 ms 166992 KB Output is correct
10 Correct 256 ms 166776 KB Output is correct
11 Correct 166 ms 166744 KB Output is correct
12 Correct 30 ms 166632 KB Output is correct
13 Incorrect 30 ms 166544 KB Output isn't correct
14 Halted 0 ms 0 KB -