oj.uz

Submission #912285

# Submission time Handle Problem Language Result Execution time Memory
912285 2024-01-19T09:36:19 Z imarn Toll (BOI17_toll) C++14
7 / 100
 273 ms 168552 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;
        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 269 ms 167788 KB Output is correct
2 Correct 31 ms 166740 KB Output is correct
3 Correct 29 ms 166748 KB Output is correct
4 Correct 30 ms 166544 KB Output is correct
5 Correct 33 ms 166740 KB Output is correct
6 Correct 33 ms 166740 KB Output is correct
7 Correct 33 ms 166740 KB Output is correct
8 Correct 273 ms 167764 KB Output is correct
9 Correct 263 ms 167496 KB Output is correct
10 Correct 250 ms 166788 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 168552 KB Output is correct
2 Correct 31 ms 166748 KB Output is correct
3 Incorrect 29 ms 166740 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 166700 KB Output is correct
2 Incorrect 29 ms 166740 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 166700 KB Output is correct
2 Incorrect 29 ms 166740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 167788 KB Output is correct
2 Correct 31 ms 166740 KB Output is correct
3 Correct 29 ms 166748 KB Output is correct
4 Correct 30 ms 166544 KB Output is correct
5 Correct 33 ms 166740 KB Output is correct
6 Correct 33 ms 166740 KB Output is correct
7 Correct 33 ms 166740 KB Output is correct
8 Correct 273 ms 167764 KB Output is correct
9 Correct 263 ms 167496 KB Output is correct
10 Correct 250 ms 166788 KB Output is correct
11 Correct 190 ms 168552 KB Output is correct
12 Correct 31 ms 166748 KB Output is correct
13 Incorrect 29 ms 166740 KB Output isn't correct
14 Halted 0 ms 0 KB -