oj.uz

Submission #807444

# Submission time Handle Problem Language Result Execution time Memory
807444 2023-08-04T17:41:05 Z idiotcomputer Toll (BOI17_toll) C++11
0 / 100
 304 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e4*5;
long long int dp[mxN][16][5];
int nidx[mxN][16][5];

int n,k;
long long int query(int a, int b){
    if (a == b){
        return 0;
    }
    int i = (int) (b/k) - (int) (a/k);
    
    
  //  cout << a << ", " << b <<" " <<i << '\n';
    if (i == 0){
        return INT_MAX;
    }
    
    i -= 1;
    long long int mini = INT_MAX;
    for (int j = 0; j < k; j++){
      //  cout << nidx[a][i][j] << " nidx lo\n";
        if (nidx[a][i][j] == -1){
            continue;
        }
        mini = min(mini, query(nidx[a][i][j],b)+dp[a][i][j]);
    }
    return mini;
}

int main()
{
     
    memset(nidx,-1,sizeof(nidx));
    
    for (int i =0; i < mxN; i++){
        for (int j = 0; j < 16; j++){
            for (int l = 0; l < 5; l++){
                dp[i][j][l] = INT_MAX;
            }
        }
    }
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m,o;
    cin >> k >> n >> m >> o;
    
    vector<vector<pair<int,int>>> connect(n);
    
    int a,b,t;
    for (int i =0; i < m; i++){
        cin >> a >> b >> t;
        connect[a].push_back({b,t});
    }
 
    for (int i = n-1; i >= 0; i--){
        for (int j =0; j < connect[i].size(); j++){
            int curr = connect[i][j].first;
            dp[i][0][curr % k] = connect[i][j].second;
            nidx[i][0][curr%k] = curr;
        }
        for (int l = 1; l < 16; l++){
       
            for (int p1 = 0; p1 < k; p1++){
                for (int p2 = 0; p2 < k; p2++){
                    if (nidx[i][l-1][p2] == -1){
                        continue;
                    }
                    if (dp[nidx[i][l-1][p2]][l-1][p1] + dp[i][l-1][p2] < dp[i][l][p1]){
                        dp[i][l][p1] = dp[nidx[i][l-1][p2]][l-1][p1] + dp[i][l-1][p2];
                        nidx[i][l][p1] = nidx[nidx[i][l-1][p2]][l-1][p1];
                    }
                }
            }
        }
    }

    for (int i =0; i < o; i++){
        cin >> a >> b;
        long long int res = query(a,b);
        if (res == INT_MAX){
            cout << "-1\n";
        } else {
            cout << res << '\n';
        }
    }
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int j =0; j < connect[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 304 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -