oj.uz

Submission #399545

# Submission time Handle Problem Language Result Execution time Memory
399545 2021-05-06T03:25:08 Z Andyvanh1 Toll (BOI17_toll) C++14
7 / 100
 249 ms 54908 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;



#define vt vector
#define pb push_back

typedef long long ll;
typedef vt<int> vi;


#define INF 2000000000

int N,M,K;

vt<vt<vt<vi>>> dp;

vt<vi> arr;
vt<vt<pair<int,int>>> adjlist;

void gen(){
    for(int f = 1; f < 17; f++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < K; j++){
                for(int l = 0; l < K; l++ ){
                    if(i+(1<<(f-1))<N) {
                        for(int a = 0; a < K; a++){
                            dp[i][j][f][l] = min(dp[i][j][f][l],dp[i][j][f - 1][a] + dp[i + (1 << (f - 1))][a][f - 1][l]);
                        }

                    }
                }
            }
        }
    }

}

int get(int i, int j, int f, int l){
    vi cur(K);
    f--;
    for(int a = 0; a < K; a++){
        cur[a] = dp[i][j][0][a];
    }
    i++;

    for(int a = 0; a < 17; a++){

        if((1<<a)&f){
            vi part(K);
            for(int b = 0; b < K; b++){
                part[b] = INF/3;
            }
            for(int b = 0; b < K; b++){
                for(int c = 0; c < K; c++){
                    if(dp[i][c][a][b]!=INF/3){
                        part[b] = min(part[b],cur[c]+dp[i][c][a][b]);
                    }
                }
            }
            i+=(1<<a);
            for(int b = 0; b < K; b++){
                cur[b] = part[b];
            }

        }

    }
    if(cur[l]==INF/3){
        return -1;
    }
    return cur[l];

}

void solve(){
    int  m, n, o;
    cin>>K>>n>>m>>o;
    N = (n-1)/K+1;
    arr.resize(N,vi(K));
    adjlist.resize(n);
    dp.resize(N,vt<vt<vi>>(K,vt<vi>(17,vi(K))));

    for(int i = 0; i < N; i++){
        for(int j = 0; j < K; j++){
            for(int l = 0; l < K; l++){
                for(int f = 0; f < 17; f++) {
                    dp[i][j][f][l] = INF / 3;
                }
            }
        }
    }


    for(int i = 0; i < m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        dp[u/K][u%K][0][v%K] = w;
    }

    gen();

    for(int i = 0; i < o; i++){
        int u,v;
        cin>>u>>v;
        cout<<get(u/K,u%K,(v/K-u/K),v%K)<<'\n';
    }

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    for(int i = 0; i < t; i++){
        solve();
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 54908 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 3 ms 1356 KB Output is correct
7 Correct 3 ms 1356 KB Output is correct
8 Correct 165 ms 54852 KB Output is correct
9 Correct 161 ms 54832 KB Output is correct
10 Correct 137 ms 54084 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 53536 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 11
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 Runtime error 1 ms 460 KB Execution killed with signal 11
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 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 54908 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 3 ms 1356 KB Output is correct
7 Correct 3 ms 1356 KB Output is correct
8 Correct 165 ms 54852 KB Output is correct
9 Correct 161 ms 54832 KB Output is correct
10 Correct 137 ms 54084 KB Output is correct
11 Correct 249 ms 53536 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Runtime error 1 ms 460 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -