oj.uz

Submission #1101921

# Submission time Handle Problem Language Result Execution time Memory
1101921 2024-10-17T07:37:59 Z doducanh Toll (BOI17_toll) C++14
100 / 100
 276 ms 250952 KB 
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=5e4+7;
const int inf=1e9+7;
vector<ii>adj[maxn];
int k,n,m,q;
int dp[maxn][25][5][5];
void mix(int target[5][5],int a[5][5],int b[5][5]){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            for(int k=0;k<5;k++){
                target[i][j]=min(target[i][j],a[i][k]+b[k][j]);
            }
        }
    }
}
void sol(void){
    cin>>k>>n>>m>>q;
    memset(dp,inf,sizeof(dp));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        dp[u/k][0][u%k][v%k]=w;
    }
    for(int i=1;i<=20;i++){
        for(int j=0;j+(1<<i)<n;j++){
            mix(dp[j][i],dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
        }
    }
    while(q--){
        int u,v;
        cin>>u>>v;
        int ans[5][5];
        int tmp[5][5];
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(i==j)ans[i][j]=0;
                else ans[i][j]=inf;
            }
        }
        for(int left=u/k,right=v/k,i=20;i>=0;i--)if(left+(1<<i)<=right){
            for(int j=0;j<5;j++){
                for(int k=0;k<5;k++){
                    tmp[j][k]=ans[j][k];
                    ans[j][k]=inf;
                }
            }
            mix(ans,tmp,dp[left][i]);
            left+=(1<<i);
        }
        cout<<(ans[u%k][v%k]==inf?-1:ans[u%k][v%k])<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 247720 KB Output is correct
2 Correct 35 ms 246092 KB Output is correct
3 Correct 35 ms 246096 KB Output is correct
4 Correct 34 ms 246096 KB Output is correct
5 Correct 36 ms 246088 KB Output is correct
6 Correct 34 ms 246264 KB Output is correct
7 Correct 35 ms 246096 KB Output is correct
8 Correct 209 ms 247620 KB Output is correct
9 Correct 252 ms 247624 KB Output is correct
10 Correct 196 ms 246172 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 248832 KB Output is correct
2 Correct 32 ms 246224 KB Output is correct
3 Correct 36 ms 246104 KB Output is correct
4 Correct 37 ms 246088 KB Output is correct
5 Correct 32 ms 246088 KB Output is correct
6 Correct 33 ms 246088 KB Output is correct
7 Correct 40 ms 246184 KB Output is correct
8 Correct 44 ms 246344 KB Output is correct
9 Correct 220 ms 247748 KB Output is correct
10 Correct 247 ms 250228 KB Output is correct
11 Correct 240 ms 248752 KB Output is correct
12 Correct 223 ms 248324 KB Output is correct
13 Correct 176 ms 250952 KB Output is correct
14 Correct 144 ms 248844 KB Output is correct
15 Correct 138 ms 248148 KB Output is correct
16 Correct 128 ms 248156 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 246056 KB Output is correct
2 Correct 35 ms 246096 KB Output is correct
3 Correct 35 ms 246088 KB Output is correct
4 Correct 34 ms 246152 KB Output is correct
5 Correct 36 ms 246088 KB Output is correct
6 Correct 38 ms 246260 KB Output is correct
7 Correct 37 ms 246360 KB Output is correct
8 Correct 37 ms 246384 KB Output is correct
9 Correct 40 ms 246344 KB Output is correct
10 Correct 237 ms 247624 KB Output is correct
11 Correct 227 ms 248648 KB Output is correct
12 Correct 216 ms 250184 KB Output is correct
13 Correct 245 ms 250440 KB Output is correct
14 Correct 221 ms 249416 KB Output is correct
15 Correct 118 ms 248136 KB Output is correct
16 Correct 125 ms 248136 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 246056 KB Output is correct
2 Correct 35 ms 246096 KB Output is correct
3 Correct 35 ms 246088 KB Output is correct
4 Correct 34 ms 246152 KB Output is correct
5 Correct 36 ms 246088 KB Output is correct
6 Correct 38 ms 246260 KB Output is correct
7 Correct 37 ms 246360 KB Output is correct
8 Correct 37 ms 246384 KB Output is correct
9 Correct 40 ms 246344 KB Output is correct
10 Correct 237 ms 247624 KB Output is correct
11 Correct 227 ms 248648 KB Output is correct
12 Correct 216 ms 250184 KB Output is correct
13 Correct 245 ms 250440 KB Output is correct
14 Correct 221 ms 249416 KB Output is correct
15 Correct 118 ms 248136 KB Output is correct
16 Correct 125 ms 248136 KB Output is correct
17 Correct 203 ms 248796 KB Output is correct
18 Correct 32 ms 246180 KB Output is correct
19 Correct 33 ms 246092 KB Output is correct
20 Correct 31 ms 246088 KB Output is correct
21 Correct 32 ms 246168 KB Output is correct
22 Correct 31 ms 246092 KB Output is correct
23 Correct 34 ms 246088 KB Output is correct
24 Correct 36 ms 246344 KB Output is correct
25 Correct 34 ms 246352 KB Output is correct
26 Correct 34 ms 246372 KB Output is correct
27 Correct 195 ms 247920 KB Output is correct
28 Correct 207 ms 250204 KB Output is correct
29 Correct 235 ms 250632 KB Output is correct
30 Correct 237 ms 249416 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 247720 KB Output is correct
2 Correct 35 ms 246092 KB Output is correct
3 Correct 35 ms 246096 KB Output is correct
4 Correct 34 ms 246096 KB Output is correct
5 Correct 36 ms 246088 KB Output is correct
6 Correct 34 ms 246264 KB Output is correct
7 Correct 35 ms 246096 KB Output is correct
8 Correct 209 ms 247620 KB Output is correct
9 Correct 252 ms 247624 KB Output is correct
10 Correct 196 ms 246172 KB Output is correct
11 Correct 236 ms 248832 KB Output is correct
12 Correct 32 ms 246224 KB Output is correct
13 Correct 36 ms 246104 KB Output is correct
14 Correct 37 ms 246088 KB Output is correct
15 Correct 32 ms 246088 KB Output is correct
16 Correct 33 ms 246088 KB Output is correct
17 Correct 40 ms 246184 KB Output is correct
18 Correct 44 ms 246344 KB Output is correct
19 Correct 220 ms 247748 KB Output is correct
20 Correct 247 ms 250228 KB Output is correct
21 Correct 240 ms 248752 KB Output is correct
22 Correct 223 ms 248324 KB Output is correct
23 Correct 176 ms 250952 KB Output is correct
24 Correct 144 ms 248844 KB Output is correct
25 Correct 138 ms 248148 KB Output is correct
26 Correct 128 ms 248156 KB Output is correct
27 Correct 35 ms 246056 KB Output is correct
28 Correct 35 ms 246096 KB Output is correct
29 Correct 35 ms 246088 KB Output is correct
30 Correct 34 ms 246152 KB Output is correct
31 Correct 36 ms 246088 KB Output is correct
32 Correct 38 ms 246260 KB Output is correct
33 Correct 37 ms 246360 KB Output is correct
34 Correct 37 ms 246384 KB Output is correct
35 Correct 40 ms 246344 KB Output is correct
36 Correct 237 ms 247624 KB Output is correct
37 Correct 227 ms 248648 KB Output is correct
38 Correct 216 ms 250184 KB Output is correct
39 Correct 245 ms 250440 KB Output is correct
40 Correct 221 ms 249416 KB Output is correct
41 Correct 118 ms 248136 KB Output is correct
42 Correct 125 ms 248136 KB Output is correct
43 Correct 203 ms 248796 KB Output is correct
44 Correct 32 ms 246180 KB Output is correct
45 Correct 33 ms 246092 KB Output is correct
46 Correct 31 ms 246088 KB Output is correct
47 Correct 32 ms 246168 KB Output is correct
48 Correct 31 ms 246092 KB Output is correct
49 Correct 34 ms 246088 KB Output is correct
50 Correct 36 ms 246344 KB Output is correct
51 Correct 34 ms 246352 KB Output is correct
52 Correct 34 ms 246372 KB Output is correct
53 Correct 195 ms 247920 KB Output is correct
54 Correct 207 ms 250204 KB Output is correct
55 Correct 235 ms 250632 KB Output is correct
56 Correct 237 ms 249416 KB Output is correct
57 Correct 276 ms 250596 KB Output is correct
58 Correct 231 ms 247624 KB Output is correct
59 Correct 233 ms 248904 KB Output is correct