Submission #836268

#	Time	Username	Problem	Language	Result	Execution time	Memory
836268		nonono	Toll (BOI17_toll)	C++14	0 / 100	64 ms	99068 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];

signed main() {
#define taskname ""

    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".ans", "w", stdout);
    }

    cin.tie(0)->sync_with_stdio(0);
    
    cin >> K >> N >> M >> O;
    
    for(int i = 1; i <= M; i ++) {
        int a, b, t;
        cin >> a >> b >> t;
        
        if(a / K + 1 == b / K) {
            up[a / K][a % K][b % K][0] = t;
            //cout << a / K << " " << a % K << " " << b % K << " " << t << "\n";
        }
    }
    
    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 ++) {
                        if(!up[i + (1 << k - 1)][j2][j3][k - 1]) continue ;
                        up[i][j1][j3][k] = up[i][j1][j2][k - 1] + up[i + (1 << k - 1)][j2][j3][k - 1]; 
                    
                        /*cout << k << " " << i << " " << j1 << " " << j2 << " " << j3 << " " << up[i][j1][j2][k - 1] << " " << 
                                                    up[i + (1 << k - 1)][j2][j3][k - 1] << " " << up[i][j1][j3][k] << "\n";*/
                    }
                }
            }
        }    
    }
    
    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 ++) {
                        if(!up[a][j][i][k]) continue ;
                        ar[i] = min(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:38:44: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |                         if(!up[i + (1 << k - 1)][j2][j3][k - 1]) continue ;
      |                                          ~~^~~
toll.cpp:39:82: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |                         up[i][j1][j3][k] = up[i][j1][j2][k - 1] + up[i + (1 << k - 1)][j2][j3][k - 1];
      |                                                                                ~~^~~
toll.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen(taskname".ans", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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