Submission #529945

#	Time	Username	Problem	Language	Result	Execution time	Memory
529945		79brue	Toll (BOI17_toll)	C++14	100 / 100	181 ms	101416 KiB

toll

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int k, n, m, q;
int sps[50002][5][5][20];

int main(){
    scanf("%d %d %d %d", &k, &n, &m, &q);
    for(int i=0; i<=n; i++) for(int j=0; j<5; j++) for(int x=0; x<5; x++) for(int y=0; y<16; y++) sps[i][j][x][y] = 1e9;

    while(m--){
        int a, b, v;
        scanf("%d %d %d", &a, &b, &v);
        sps[a/k][a%k][b%k][0] = min(sps[a/k][a%k][b%k][0], v);
    }

    for(int d=0; d<16; d++){
        for(int i=0; i<=n/k; i++){
            for(int x=0; x<k; x++) for(int y=0; y<k; y++) for(int z=0; z<k; z++){
                sps[i][x][z][d+1] = min(sps[i][x][z][d+1], sps[i][x][y][d] + (i+(1<<d) >= n ? 0 : sps[i+(1<<d)][y][z][d]));
            }
        }
    }

    while(q--){
        int S, E;
        scanf("%d %d", &S, &E);
        if(S/k >= E/k){
            puts("-1");
            continue;
        }

        vector<int> dist (k, 1e9);
        dist[S%k] = 0;

        int sg = S/k, eg = E/k, gd = eg - sg;
        for(int d=0; d<16; d++){
            if((gd >> d) & 1){
                vector<int> dist2 (k, 1e9);
                for(int i=0; i<k; i++){
                    for(int j=0; j<k; j++){
                        dist2[j] = min(dist2[j], dist[i] + sps[sg][i][j][d]);
                    }
                }
                sg += 1<<d;
                dist = dist2;
            }
        }

        printf("%d\n", dist[E%k]>=1e9 ? -1 : dist[E%k]);
    }
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %d %d %d", &k, &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d %d %d", &a, &b, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d %d", &S, &E);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44