oj.uz

Submission #912287

# Submission time Handle Problem Language Result Execution time Memory
912287 2024-01-19T09:38:49 Z imarn Toll (BOI17_toll) C++14
7 / 100
 91 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];int k;
void pre(int i,int j,int ii,int jj,int iii,int jjj){
    for(int x=0;x<k;x++){
        for(int y=0;y<k;y++){
            for(int z=0;z<k;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 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 72 ms 166748 KB Output is correct
2 Correct 29 ms 166736 KB Output is correct
3 Correct 29 ms 166528 KB Output is correct
4 Correct 29 ms 166744 KB Output is correct
5 Correct 29 ms 166740 KB Output is correct
6 Correct 30 ms 166992 KB Output is correct
7 Correct 32 ms 166740 KB Output is correct
8 Correct 77 ms 166736 KB Output is correct
9 Correct 70 ms 166740 KB Output is correct
10 Correct 56 ms 166748 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 166740 KB Output is correct
2 Correct 34 ms 166736 KB Output is correct
3 Incorrect 29 ms 166748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 166748 KB Output is correct
2 Correct 29 ms 166736 KB Output is correct
3 Correct 29 ms 166528 KB Output is correct
4 Correct 29 ms 166744 KB Output is correct
5 Correct 29 ms 166740 KB Output is correct
6 Correct 30 ms 166992 KB Output is correct
7 Correct 32 ms 166740 KB Output is correct
8 Correct 77 ms 166736 KB Output is correct
9 Correct 70 ms 166740 KB Output is correct
10 Correct 56 ms 166748 KB Output is correct
11 Correct 91 ms 166740 KB Output is correct
12 Correct 34 ms 166736 KB Output is correct
13 Incorrect 29 ms 166748 KB Output isn't correct
14 Halted 0 ms 0 KB -