oj.uz

Submission #807497

# Submission time Handle Problem Language Result Execution time Memory
807497 2023-08-04T18:16:01 Z idiotcomputer Toll (BOI17_toll) C++11
46 / 100
 3000 ms 38136 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 = 0;
    for (i = 0; i < 16; i++){
        if (nidx[a][i][0] == -1 || nidx[a][i][0] > b){
            break;
        }
    }

    
    
 //   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 << dp[a][i][j] << " nidx lo\n";
        if (dp[a][i][j] == INT_MAX){
            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;
    
    for (int i =n-1; i >= 0; i--){
        int g = i/k;
        if (g == (n-1)/k){
            continue;
        }
       // cout << i << " " << g << '\n';
        for (int j = 0; j < k; j++){
            if ((g+1)*k+j >= n){
                break;
            }
            nidx[i][0][j] = (g+1)*k+j;
        } 
        for (int j = 1; j < 16; j++){
            for (int l = 0; l < k; l++){
                if (nidx[i][j-1][0] == -1){
                    continue;
                }   
                nidx[i][j][l] = nidx[nidx[i][j-1][0]][j-1][l];
            }
        }
    }
    
    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 (dp[i][l-1][p2] == INT_MAX){
                        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';
    }
    cout << '\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 << nidx[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:103: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]
  103 |         for (int j =0; j < connect[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35280 KB Output is correct
2 Correct 12 ms 31636 KB Output is correct
3 Correct 12 ms 31556 KB Output is correct
4 Correct 12 ms 31572 KB Output is correct
5 Correct 13 ms 31640 KB Output is correct
6 Correct 13 ms 31684 KB Output is correct
7 Correct 13 ms 31640 KB Output is correct
8 Correct 43 ms 35260 KB Output is correct
9 Correct 42 ms 35196 KB Output is correct
10 Correct 35 ms 32888 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 36032 KB Output is correct
2 Correct 13 ms 31572 KB Output is correct
3 Correct 12 ms 31528 KB Output is correct
4 Correct 12 ms 31572 KB Output is correct
5 Correct 13 ms 31632 KB Output is correct
6 Correct 13 ms 31624 KB Output is correct
7 Correct 15 ms 31772 KB Output is correct
8 Correct 19 ms 31820 KB Output is correct
9 Correct 41 ms 35212 KB Output is correct
10 Correct 1220 ms 37616 KB Output is correct
11 Correct 114 ms 36044 KB Output is correct
12 Correct 61 ms 35552 KB Output is correct
13 Execution timed out 3076 ms 37532 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 12 ms 31632 KB Output is correct
3 Correct 12 ms 31516 KB Output is correct
4 Correct 12 ms 31636 KB Output is correct
5 Correct 12 ms 31540 KB Output is correct
6 Correct 13 ms 31700 KB Output is correct
7 Correct 13 ms 31648 KB Output is correct
8 Correct 15 ms 31772 KB Output is correct
9 Correct 15 ms 31644 KB Output is correct
10 Correct 39 ms 35140 KB Output is correct
11 Correct 70 ms 35776 KB Output is correct
12 Correct 86 ms 37344 KB Output is correct
13 Correct 91 ms 37952 KB Output is correct
14 Correct 81 ms 36684 KB Output is correct
15 Correct 138 ms 34712 KB Output is correct
16 Correct 154 ms 34764 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 12 ms 31632 KB Output is correct
3 Correct 12 ms 31516 KB Output is correct
4 Correct 12 ms 31636 KB Output is correct
5 Correct 12 ms 31540 KB Output is correct
6 Correct 13 ms 31700 KB Output is correct
7 Correct 13 ms 31648 KB Output is correct
8 Correct 15 ms 31772 KB Output is correct
9 Correct 15 ms 31644 KB Output is correct
10 Correct 39 ms 35140 KB Output is correct
11 Correct 70 ms 35776 KB Output is correct
12 Correct 86 ms 37344 KB Output is correct
13 Correct 91 ms 37952 KB Output is correct
14 Correct 81 ms 36684 KB Output is correct
15 Correct 138 ms 34712 KB Output is correct
16 Correct 154 ms 34764 KB Output is correct
17 Correct 75 ms 35888 KB Output is correct
18 Correct 13 ms 31572 KB Output is correct
19 Correct 11 ms 31572 KB Output is correct
20 Correct 13 ms 31632 KB Output is correct
21 Correct 12 ms 31572 KB Output is correct
22 Correct 12 ms 31540 KB Output is correct
23 Correct 14 ms 31644 KB Output is correct
24 Correct 15 ms 31644 KB Output is correct
25 Correct 37 ms 31808 KB Output is correct
26 Correct 26 ms 31700 KB Output is correct
27 Correct 40 ms 35112 KB Output is correct
28 Correct 262 ms 37508 KB Output is correct
29 Correct 257 ms 38136 KB Output is correct
30 Correct 112 ms 36684 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 35280 KB Output is correct
2 Correct 12 ms 31636 KB Output is correct
3 Correct 12 ms 31556 KB Output is correct
4 Correct 12 ms 31572 KB Output is correct
5 Correct 13 ms 31640 KB Output is correct
6 Correct 13 ms 31684 KB Output is correct
7 Correct 13 ms 31640 KB Output is correct
8 Correct 43 ms 35260 KB Output is correct
9 Correct 42 ms 35196 KB Output is correct
10 Correct 35 ms 32888 KB Output is correct
11 Correct 75 ms 36032 KB Output is correct
12 Correct 13 ms 31572 KB Output is correct
13 Correct 12 ms 31528 KB Output is correct
14 Correct 12 ms 31572 KB Output is correct
15 Correct 13 ms 31632 KB Output is correct
16 Correct 13 ms 31624 KB Output is correct
17 Correct 15 ms 31772 KB Output is correct
18 Correct 19 ms 31820 KB Output is correct
19 Correct 41 ms 35212 KB Output is correct
20 Correct 1220 ms 37616 KB Output is correct
21 Correct 114 ms 36044 KB Output is correct
22 Correct 61 ms 35552 KB Output is correct
23 Execution timed out 3076 ms 37532 KB Time limit exceeded
24 Halted 0 ms 0 KB -