Submission #626660

#	Time	Username	Problem	Language	Result	Execution time	Memory
626660		MohamedFaresNebili	Toll (BOI17_toll)	C++14	100 / 100	329 ms	101468 KiB

toll

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int LOG = 20;

            int K, N, M, Q;
            array<array<int, 5>, 5> P[50005][20];
            array<array<int, 5>, 5> merge(array<array<int, 5>, 5>  A,
                                          array<array<int, 5>, 5>  B) {
                array<array<int, 5>, 5> res;
                for(int l = 0; l < K; l++)
                    for(int i = 0; i < K; i++)
                        res[l][i] = 1e9 + 7;
                for(int l = 0; l < K; l++)
                    for(int i = 0; i < K; i++)
                        for(int j = 0; j < K; j++)
                            res[l][i] = min(res[l][i], A[l][j] + B[j][i]);
                return res;
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> K >> N >> M >> Q;
                for(int l = 0; l < N; l++)
                    for(int i = 0; i < LOG; i++)
                        for(int j = 0; j < K; j++)
                            for(int e = 0; e < K; e++)
                                P[l][i][j][e] = 1e9 + 7;
                for(int l = 0; l < M; l++) {
                    int U, V, C; cin >> U >> V >> C;
                    P[U / K][0][U % K][V % K] = C;
                }
                for(int l = 1; l < LOG; l++) {
                    for(int i = 0; i + (1 << l) < (N + K - 1) / K; i++) {
                        P[i][l] = merge(P[i][l - 1], P[i + (1 << l - 1)][l - 1]);
                    }
                }
                while(Q--) {
                    int U, V; cin >> U >> V;
                    int X = U / K, Y = V / K;
                    array<array<int, 5>, 5> res;
                    for(int l = 0; l < K; l++) {
                        for(int i = 0; i < K; i++)
                            res[l][i] = 1e9 + 7;
                        res[l][l] = 0;
                    }
                    for(int l = LOG - 1; ~l; l--) {
                        if(X + (1 << l) > Y) continue;
                        res = merge(res, P[X][l]);
                        X += (1 << l);
                    }
                    cout << (res[U % K][V % K] == 1e9 + 7 ? -1 : res[U % K][V % K]) << "\n";
                }
                return 0;
            }

Compilation message (stderr)

toll.cpp: In function 'int32_t main()':
toll.cpp:48:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |                         P[i][l] = merge(P[i][l - 1], P[i + (1 << l - 1)][l - 1]);
      |                                                                  ~~^~~

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