oj.uz

Submission #807459

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

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

int n,k;
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;
    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 = (int) min((long long int) mini, (long long int) 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 =0; i < 4*1e8; i++){
        continue;
    }*/
    
 //   cout << "LEELL\n";
/*    for (int i =0; i < n; i++){
        cout << i << ": \n";
        for (int j = 0; j < 5; j++){
            for (int l = 0; l < k; l++){
                cout << dp[i][j][l] << " ";
            }
            cout << '\n';
        }
        cout << '\n';
    }*/
    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++){
       /*     if (nidx[a][l-1][0] == -1){
                break;
            }*/
            for (int p1 = 0; p1 < k; p1++){
                for (int p2 = 0; p2 < k; p2++){
                    if (nidx[i][l-1][p2] == -1){
                        continue;
                    }
               //     cout << (long long int) dp[nidx[i][l-1][p2]][l-1][p1] + dp[i][l-1][p2] << '\n';
                    if ((long long int) dp[nidx[i][l-1][p2]][l-1][p1] + dp[i][l-1][p2] < (long long int) 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];
                    }
                  //  dp[i][l][p1] = min(dp[i][l][p1],dp[nidx[i][l-1][p2]][l-1][p1] + dp[i][l-1][p2]);
                }
            }
        }
    }

   /* for (int i =0; i < n; i++){
        cout << i << ": \n";
        for (int j = 0; j < 5; j++){
            for (int l = 0; l < k; l++){
                if (dp[i][j][l] == INT_MAX){
                    cout << "0 ";
                } else {
                    cout << dp[i][j][l] << " ";
                }
            }
            cout << '\n';
        }
        cout << '\n';
    }*/
    //return 0;
    for (int i =0; i < o; i++){
        cin >> a >> b;
        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:75: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]
   75 |         for (int j =0; j < connect[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 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 298 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 15 ms 31576 KB Output is correct
2 Incorrect 12 ms 31568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Incorrect 12 ms 31568 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 287 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -