Submission #807514

#	Time	Username	Problem	Language	Result	Execution time	Memory
807514		idiotcomputer	Toll (BOI17_toll)	C++11	100 / 100	121 ms	38860 KiB

toll

#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 g, int b, int vals[]){
    
    int i = 0;
    for (i = 0; i < 16; i++){
        if (nidx[g*k][i][0] == -1 || nidx[g*k][i][0] > b){
            break;
        }
    }
    if (i == 0){
        return vals[b % k];
    }
    i -= 1;
    
    int nvals[k];
    for (int j =0; j  <k; j++){
        nvals[j] = INT_MAX;
    }
    
    for (int j =0; j < k; j++){
        if (vals[j] == INT_MAX){
            continue;
        }
        for (int l = 0; l < k; l++){
            if (dp[g*k+j][i][l] == INT_MAX){
                continue;
            }
            nvals[l] = min(nvals[l], dp[g*k+j][i][l]+vals[j]);
        }
    }
    
    return query(nidx[g*k][i][0] / k, b, nvals);
}

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){
                    break;
                }   
                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;
        }
        bool has;
        for (int l = 1; l < 16; l++){
       /*     if (nidx[a][l-1][0] == -1){
                break;
            }*/
            has = false;
            for (int p1 = 0; p1 < k; p1++){
                for (int p2 = 0; p2 < k; p2++){
                    if (dp[i][l-1][p2] == INT_MAX){
                        continue;
                    }
                    has = true;
               //     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]);
                }
                if (!has){
                    break;
                }
            }
            if (!has){
                break;
            }
        }
    }
 /*   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;
    int temp[k];
    for (int i =0; i < o; i++){
        cin >> a >> b;
        for (int j =0; j < k; j++){
            temp[j] = INT_MAX;
        }
        temp[a%k] = 0;
        int res = query(a/k,b,temp);
        if (res == INT_MAX){
            cout << "-1\n";
        } else {
            cout << res << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:106: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]
  106 |         for (int j =0; j < connect[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44