oj.uz

Submission #529943

# Submission time Handle Problem Language Result Execution time Memory
529943 2022-02-24T06:14:20 Z 79brue Toll (BOI17_toll) C++14
7 / 100
 120 ms 99128 KB 
#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("0");
            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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 98376 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2256 KB Output is correct
7 Correct 2 ms 2224 KB Output is correct
8 Correct 83 ms 99000 KB Output is correct
9 Correct 82 ms 99128 KB Output is correct
10 Correct 61 ms 98168 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 98116 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 98376 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2256 KB Output is correct
7 Correct 2 ms 2224 KB Output is correct
8 Correct 83 ms 99000 KB Output is correct
9 Correct 82 ms 99128 KB Output is correct
10 Correct 61 ms 98168 KB Output is correct
11 Correct 120 ms 98116 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Incorrect 1 ms 204 KB Output isn't correct
14 Halted 0 ms 0 KB -