Submission #836279

#	Time	Username	Problem	Language	Result	Execution time	Memory
836279		nonono	Toll (BOI17_toll)	C++14	100 / 100	137 ms	99144 KiB

toll

#include <bits/stdc++.h>
using namespace std;

const int INF = 5e8;
const int LOG = 20;
const int mxN = 50005;

int K, N, M, O;
int up[mxN][5][5][LOG];

void minimize(int &a, int b) {
    if(a > b) a = b;
}

signed main() {

    cin.tie(0)->sync_with_stdio(0);
    
    cin >> K >> N >> M >> O;
    
    for(int k = 0; k <= 18; k ++) {
        for(int i = 0; i <= (N - 1) / K; i ++) {
            for(int j1= 0; j1 < K; j1 ++) {
                for(int j2 = 0; j2 < K; j2 ++) {
                    up[i][j1][j2][k] = INF;
                }
            }
        }
    }
    
    for(int i = 1; i <= M; i ++) {
        int a, b, t;
        cin >> a >> b >> t;
        
        if(a / K + 1 == b / K) {
            minimize(up[a / K][a % K][b % K][0], t);
        }
    }
    
    for(int k = 1; (1 << k) <= (N - 1) / K; k ++) {
        for(int i = 0; i + (1 << k) <= (N - 1) / K; i ++) {
            for(int j1 = 0; j1 < K; j1 ++) {
                for(int j2 = 0; j2 < K; j2 ++) {
                    for(int j3 = 0; j3 < K; j3 ++) {
                        minimize(up[i][j1][j3][k], up[i][j1][j2][k - 1] + up[i + (1 << k - 1)][j2][j3][k - 1]); 
                    }
                }
            }
        }    
    }
    
    while(O --) {
        int a, b;
        cin >> a >> b;
        
        int typeA = a % K;
        int typeB = b % K;
        
        a /= K;
        b /= K;
        
        vector<int> ar(K);
        
        for(int i = 0; i < K; i ++) ar[i] = INF;
        ar[typeA] = 0;
        
        int depth = b - a;
        for(int k = 0; k <= 18; k ++) {
            if(depth >> k & 1) {
                
                vector<int> _ar(K);
                
                for(int i = 0; i < K; i ++) {
                    _ar[i] = ar[i];
                    ar[i] = INF;    
                }
                
                for(int i = 0; i < K; i ++) {
                    for(int j = 0; j < K; j ++) {
                        minimize(ar[i], _ar[j] + up[a][j][i][k]);
                    }
                }
                
                a += (1 << k);           
            }
        }
        
        if(ar[typeB] >= INF) cout << -1 << "\n"; else cout << ar[typeB] << "\n";
    }
    
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:45:90: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |                         minimize(up[i][j1][j3][k], up[i][j1][j2][k - 1] + up[i + (1 << k - 1)][j2][j3][k - 1]);
      |                                                                                        ~~^~~

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