oj.uz

Submission #927325

# Submission time Handle Problem Language Result Execution time Memory
927325 2024-02-14T18:04:01 Z noyancanturk Toll (BOI17_toll) C++17
100 / 100
 80 ms 158896 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=5e4+100;
#else
    const int lim=3e3+3;
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
const int mod=998244353;
//const int mod=(1ll<<61)-1;
    
using pii=pair<int,int>;

int dist[16][lim][5][5];

inline void solve(){
    int k,n,m,o;
    cin>>k>>n>>m>>o;
    for(int i=0;i<16;i++){
        for(int j=0;j<=n/k;j++){
            for(int ii=0;ii<k;ii++){
                for(int jj=0;jj<k;jj++){
                    dist[i][j][ii][jj]=INT_MAX;
                }
            }
        }
    }
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        dist[0][x/k][x%k][y%k]=z;
    }
    for(int jp=1;jp<16;jp++){
        for(int i=0;i<=n/k;i++){
            if(lim<=i+(1<<jp))break;
            for(int l=0;l<k;l++){
                for(int r=0;r<k;r++){
                    for(int mid=0;mid<k;mid++){
                        dist[jp][i][l][r]=min(
                            dist[jp][i][l][r],
                            dist[jp-1][i][l][mid]+
                            dist[jp-1][i+(1<<(jp-1))][mid][r]
                        );
                    }
                }
            }
        }
    }
    while(o--){
        int a,b;
        cin>>a>>b;
        int cur=a/k,dest=b/k;
        if(dest<=cur){
            cout<<"-1\n";
            continue;
        }
        int*now=new int[k],*to=new int[k];
        for(int i=0;i<k;i++){
            now[i]=to[i]=INT_MAX;
        }
        now[a%k]=0;
        for(int jp=15;0<=jp;jp--){
            if(cur+(1<<jp)<=dest){
                for(int i=0;i<k;i++){
                    to[i]=INT_MAX;
                    for(int j=0;j<k;j++){
                        to[i]=min(to[i],
                        now[j]+dist[jp][cur][j][i]);
                    }
                }
                cur+=1<<jp;
                swap(now,to);
            }
        }
        if(now[b%k]^INT_MAX){
            cout<<now[b%k]<<"\n";
        }else{
            cout<<"-1\n";
        }
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else

#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 158896 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 4 ms 31068 KB Output is correct
4 Correct 4 ms 31068 KB Output is correct
5 Correct 5 ms 35548 KB Output is correct
6 Correct 5 ms 35420 KB Output is correct
7 Correct 5 ms 35420 KB Output is correct
8 Correct 49 ms 158704 KB Output is correct
9 Correct 48 ms 158800 KB Output is correct
10 Correct 36 ms 157920 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 111696 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 4 ms 31192 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 3 ms 31068 KB Output is correct
6 Correct 3 ms 31068 KB Output is correct
7 Correct 7 ms 36124 KB Output is correct
8 Correct 7 ms 31956 KB Output is correct
9 Correct 48 ms 158804 KB Output is correct
10 Correct 59 ms 87688 KB Output is correct
11 Correct 46 ms 111812 KB Output is correct
12 Correct 36 ms 86608 KB Output is correct
13 Correct 46 ms 54612 KB Output is correct
14 Correct 30 ms 61776 KB Output is correct
15 Correct 33 ms 53328 KB Output is correct
16 Correct 34 ms 53328 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 4 ms 31068 KB Output is correct
6 Correct 4 ms 35548 KB Output is correct
7 Correct 4 ms 31324 KB Output is correct
8 Correct 5 ms 31260 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 46 ms 158060 KB Output is correct
11 Correct 41 ms 111032 KB Output is correct
12 Correct 44 ms 86864 KB Output is correct
13 Correct 45 ms 87132 KB Output is correct
14 Correct 40 ms 86572 KB Output is correct
15 Correct 31 ms 53072 KB Output is correct
16 Correct 31 ms 53136 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31068 KB Output is correct
2 Correct 3 ms 31068 KB Output is correct
3 Correct 3 ms 31068 KB Output is correct
4 Correct 3 ms 31068 KB Output is correct
5 Correct 4 ms 31068 KB Output is correct
6 Correct 4 ms 35548 KB Output is correct
7 Correct 4 ms 31324 KB Output is correct
8 Correct 5 ms 31260 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 46 ms 158060 KB Output is correct
11 Correct 41 ms 111032 KB Output is correct
12 Correct 44 ms 86864 KB Output is correct
13 Correct 45 ms 87132 KB Output is correct
14 Correct 40 ms 86572 KB Output is correct
15 Correct 31 ms 53072 KB Output is correct
16 Correct 31 ms 53136 KB Output is correct
17 Correct 47 ms 111344 KB Output is correct
18 Correct 3 ms 31064 KB Output is correct
19 Correct 4 ms 31068 KB Output is correct
20 Correct 4 ms 31068 KB Output is correct
21 Correct 4 ms 31064 KB Output is correct
22 Correct 3 ms 31216 KB Output is correct
23 Correct 6 ms 35676 KB Output is correct
24 Correct 5 ms 31392 KB Output is correct
25 Correct 6 ms 31580 KB Output is correct
26 Correct 6 ms 31580 KB Output is correct
27 Correct 46 ms 158292 KB Output is correct
28 Correct 46 ms 86972 KB Output is correct
29 Correct 48 ms 87380 KB Output is correct
30 Correct 43 ms 86608 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 158896 KB Output is correct
2 Correct 4 ms 31068 KB Output is correct
3 Correct 4 ms 31068 KB Output is correct
4 Correct 4 ms 31068 KB Output is correct
5 Correct 5 ms 35548 KB Output is correct
6 Correct 5 ms 35420 KB Output is correct
7 Correct 5 ms 35420 KB Output is correct
8 Correct 49 ms 158704 KB Output is correct
9 Correct 48 ms 158800 KB Output is correct
10 Correct 36 ms 157920 KB Output is correct
11 Correct 55 ms 111696 KB Output is correct
12 Correct 4 ms 31064 KB Output is correct
13 Correct 4 ms 31192 KB Output is correct
14 Correct 3 ms 31068 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 31068 KB Output is correct
17 Correct 7 ms 36124 KB Output is correct
18 Correct 7 ms 31956 KB Output is correct
19 Correct 48 ms 158804 KB Output is correct
20 Correct 59 ms 87688 KB Output is correct
21 Correct 46 ms 111812 KB Output is correct
22 Correct 36 ms 86608 KB Output is correct
23 Correct 46 ms 54612 KB Output is correct
24 Correct 30 ms 61776 KB Output is correct
25 Correct 33 ms 53328 KB Output is correct
26 Correct 34 ms 53328 KB Output is correct
27 Correct 3 ms 31068 KB Output is correct
28 Correct 3 ms 31068 KB Output is correct
29 Correct 3 ms 31068 KB Output is correct
30 Correct 3 ms 31068 KB Output is correct
31 Correct 4 ms 31068 KB Output is correct
32 Correct 4 ms 35548 KB Output is correct
33 Correct 4 ms 31324 KB Output is correct
34 Correct 5 ms 31260 KB Output is correct
35 Correct 5 ms 31324 KB Output is correct
36 Correct 46 ms 158060 KB Output is correct
37 Correct 41 ms 111032 KB Output is correct
38 Correct 44 ms 86864 KB Output is correct
39 Correct 45 ms 87132 KB Output is correct
40 Correct 40 ms 86572 KB Output is correct
41 Correct 31 ms 53072 KB Output is correct
42 Correct 31 ms 53136 KB Output is correct
43 Correct 47 ms 111344 KB Output is correct
44 Correct 3 ms 31064 KB Output is correct
45 Correct 4 ms 31068 KB Output is correct
46 Correct 4 ms 31068 KB Output is correct
47 Correct 4 ms 31064 KB Output is correct
48 Correct 3 ms 31216 KB Output is correct
49 Correct 6 ms 35676 KB Output is correct
50 Correct 5 ms 31392 KB Output is correct
51 Correct 6 ms 31580 KB Output is correct
52 Correct 6 ms 31580 KB Output is correct
53 Correct 46 ms 158292 KB Output is correct
54 Correct 46 ms 86972 KB Output is correct
55 Correct 48 ms 87380 KB Output is correct
56 Correct 43 ms 86608 KB Output is correct
57 Correct 65 ms 72532 KB Output is correct
58 Correct 49 ms 158724 KB Output is correct
59 Correct 49 ms 111696 KB Output is correct