Submission #1273595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273595		_filya_	Toll (BOI17_toll)	C++20	100 / 100	111 ms	71540 KiB

toll

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e4 + 50;
const ll inf = 1e10;

vector<vector<ll>> dat[20][N];
ll mask[N];
vector<array<int, 3>> G[N];
int k, n, m, q;

vector<vector<ll>> I() {
    vector<vector<ll>> res(k, vector<ll>(k, inf));
    for (int i = 0; i < k; i++) res[i][i] = 0;
    return res;
} 

void divide(int l, int r, int lvl) {
    if (l == r) return;
    int m = (r + l) / 2;
    dat[lvl][m] = I();
    for (int i = m - 1; i >= l; i--) {
        dat[lvl][i].assign(k, vector<ll>(k, inf));
        for (int x = 0; x < k; x++) {
            for (auto u : G[i]) {
                dat[lvl][i][u[0]][x] = min(dat[lvl][i][u[0]][x], dat[lvl][i + 1][u[1]][x] + u[2]);
            }
        }
       
    }
    for (int i = m + 1; i <= r; i++) {
        dat[lvl][i].assign(k, vector<ll>(k, inf));
        for (int x = 0; x < k; x++) {
            for (auto u : G[i - 1]) {
                dat[lvl][i][u[1]][x] = min(dat[lvl][i][u[1]][x], dat[lvl][i - 1][u[0]][x] + u[2]);
            }
        }
    }
    for (int i = m + 1; i <= r; i++) mask[i] ^= (1 << lvl);
    divide(l, m, lvl + 1); divide(m + 1, r, lvl + 1);
}

int main()
{
// 	ifstream cin("input.txt");
//     ofstream cout("output.txt");
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> k >> n >> m >> q;
    n = (n + k - 1) / k * k;
    for (int i = 0; i < m; i++) {
        int a, b, t; cin >> a >> b >> t;
        G[a / k].push_back({a % k, b % k, t});
    }
    divide(0, n / k - 1, 0);
    while(q--) {
        int a, b; cin >> a >> b;
        if (a / k == b / k) {
            cout << "-1\n";
        } else {
            int lvl = __builtin_ctz(mask[a / k] ^ mask[b / k]);
            ll ans = inf;
            for (int x = 0; x < k; x++) ans = min(ans, dat[lvl][a / k][a % k][x] + dat[lvl][b / k][b % k][x]);
            cout << (ans == inf ? -1 : ans) << '\n';
        }
    }
}

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