Submission #694114

#	Time	Username	Problem	Language	Result	Execution time	Memory
694114		CDuong	Toll (BOI17_toll)	C++17	100 / 100	358 ms	163296 KiB

toll

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname "disrupt"
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
using namespace std;

const int mxN = 5e4 + 5;
const int mod = 1e9 + 7;
const int lim = 16;
const ll oo = 1e18;

struct matrix {
    ll a[5][5];

    matrix() {memset(a, 0x3f, sizeof a);}

    matrix operator + (const matrix &o) {
        matrix res;
        for(int i = 0; i < 5; ++i)
            for(int j = 0; j < 5; ++j)
                for(int k = 0; k < 5; ++k) {
                    if(a[i][j] > oo || o.a[j][k] > oo)
                        continue;
                    res.a[i][k] = min(res.a[i][k], a[i][j] + o.a[j][k]);
                }
        return res;
    }
};

int n, m, k, q;
int par[mxN][lim];
matrix path[mxN][lim];

void solve() {
    cin >> k >> n >> m >> q;
    for(int i = 0; i < n; ++i)
        par[i][0] = i + 1;
    par[n][0] = n;
    for(int i = 1; i <= m; ++i) {
        int u, v, t;
        cin >> u >> v >> t;
        path[u / k][0].a[u % k][v % k] = t;
    }
    for(int i = 1; i < lim; ++i) {
        for(int j = 0; j * k <= n; ++j) {
            par[j][i] = par[par[j][i - 1]][i - 1];
            path[j][i] = path[j][i - 1] + path[par[j][i - 1]][i - 1];
        }
    }
    while(q--) {
        int a, b;
        cin >> a >> b;
        if(b < a) {
            cout << "-1\n";
            continue;
        }
        if(a == b) {
            cout << "0\n";
            continue;
        }
        matrix res;
        for(int i = 0; i < 5; ++i)
            res.a[i][i] = 0;
        int floor_a = a / k, floor_b = b / k;
        for(int i = lim - 1; i >= 0; --i) {
            int en = floor_a + (1 << i);
            if(en <= floor_b) {
                res = res + path[floor_a][i];
                floor_a = par[floor_a][i];
            }
        }
        ll ans = res.a[a % k][b % k];
        if(ans > oo)
            ans = -1;
        cout << ans << "\n";
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".in", "r"))
        assert(freopen(taskname".in", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
    auto end = chrono::high_resolution_clock::now();
    cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
    cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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