oj.uz

Submission #912323

# Submission time Handle Problem Language Result Execution time Memory
912323 2024-01-19T10:00:20 Z imarn Toll (BOI17_toll) C++14
7 / 100
 99 ms 166812 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][5]={0},tmp[5][5]={0};
    while(o--){
        int a,b;cin>>a>>b;
        for(int i=0;i<k;i++)for(int j=0;j<k;j++)ans[i][i]=0;
        int cur=a/k,dest=b/k;
        for(int i=16;i>=0;i--){
            if(cur+(1<<i)<=dest){
                for(int x=0;x<k;x++)for(int y=0;y<k;y++)tmp[x][y]=1e15;
                for(int x=0;x<k;x++){
                for(int y=0;y<k;y++){
                    for(int z=0;z<k;z++){
                        tmp[x][y]=min(tmp[x][y],ans[x][z]+dp[cur][i][z][y]);
                    }
                }
                }for(int x=0;x<k;x++)for(int y=0;y<k;y++)ans[x][y]=tmp[x][y];
                cur+=(1<<i);
            }
        }cout<<(ans[a%k][b%k]==1e15?-1:ans[a%k][b%k])<<'\n';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 166736 KB Output is correct
2 Correct 29 ms 166740 KB Output is correct
3 Correct 29 ms 166576 KB Output is correct
4 Correct 31 ms 166740 KB Output is correct
5 Correct 31 ms 166548 KB Output is correct
6 Correct 29 ms 166748 KB Output is correct
7 Correct 30 ms 166744 KB Output is correct
8 Correct 77 ms 166748 KB Output is correct
9 Correct 71 ms 166776 KB Output is correct
10 Correct 54 ms 166812 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 166772 KB Output is correct
2 Correct 30 ms 166740 KB Output is correct
3 Incorrect 29 ms 166548 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 166728 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 30 ms 166728 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 74 ms 166736 KB Output is correct
2 Correct 29 ms 166740 KB Output is correct
3 Correct 29 ms 166576 KB Output is correct
4 Correct 31 ms 166740 KB Output is correct
5 Correct 31 ms 166548 KB Output is correct
6 Correct 29 ms 166748 KB Output is correct
7 Correct 30 ms 166744 KB Output is correct
8 Correct 77 ms 166748 KB Output is correct
9 Correct 71 ms 166776 KB Output is correct
10 Correct 54 ms 166812 KB Output is correct
11 Correct 99 ms 166772 KB Output is correct
12 Correct 30 ms 166740 KB Output is correct
13 Incorrect 29 ms 166548 KB Output isn't correct
14 Halted 0 ms 0 KB -