Submission #1222310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222310		j_vdd16	Toll (BOI17_toll)	C++20	7 / 100	132 ms	71264 KiB

toll

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <chrono>
#include <bit>
#include <climits>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

signed main() {
    int k, n, m, o;
    cin >> k >> n >> m >> o;

    int l = n / k + 1;

    const int P = 16;
    vector<vector<vvi>> dp(l, vector<vvi>(P, vvi(k, vi(k, LLONG_MAX / 2))));
    loop(i, m) {
        int a, b, t;
        cin >> a >> b >> t;

        dp[a / k][0][a % k][b % k] = t;
    }

    for (int p = 1; p < P; p++) {
        for (int layer = 0; layer < l; layer++) {
            if (layer + (1 << p) >= l)
                continue;

            const vvi& connector1 = dp[layer][p - 1];
            const vvi& connector2 = dp[min(l, layer + (1 << (p - 1)))][p - 1];
            vvi& connector = dp[layer][p];
            for (int i1 = 0; i1 < k; i1++) {
                for (int i2 = 0; i2 < k; i2++) {
                    for (int i3 = 0; i3 < k; i3++) {
                        connector[i1][i3] = min(connector[i1][i3], connector1[i1][i2] + connector2[i2][i3]);
                    }
                }
            }
        }
    }

    loop(order, o) {
        int a, b;
        cin >> a >> b;

        int l1 = a / k;
        int l2 = b / k;

        if (l1 == l2) {
            cout << 0 << endl;
            continue;
        }
        else if (l1 >= l2) {
            cout << -1 << endl;
            continue;
        }

        vi cost(k, LLONG_MAX / 2);
        cost[a % k] = 0;

        for (int p = P - 1; p >= 0; p--) {
            int diff = l2 - l1;
            if ((diff & (1 << p)) == 0)
                continue;
                
            const vvi& connector = dp[l1][p];
            vi newCost(k, LLONG_MAX / 2);
            for (int i = 0; i < k; i++) {
                for (int j = 0; j < k; j++) {
                    newCost[j] = min(newCost[j], cost[i] + connector[i][j]);
                }
            }

            swap(cost, newCost);
            l1 += (1 << p);
        }
        
        int ans = cost[b % k];
        if (ans == LLONG_MAX / 2) 
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
}

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