Submission #629592

#	Time	Username	Problem	Language	Result	Execution time	Memory
629592		Duy_e	Toll (BOI17_toll)	C++14	100 / 100	1479 ms	14596 KiB

toll

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 5e4 + 5;
const long long block = 200;

#define data array<array<ll, 5>, 5>

int n, m, k, q, id[N];

vector <pii> d[N];

struct seg {
    data f;
    int l, r;

    void set(ll val) {
        for (int u = 0; u < 5; u ++) for (int v = 0; v < 5; v ++) f[u][v] = val;
    }  

    void init(int i) {
        set(INF);
        for (int j = 0; j < 5; j ++) f[j][j] = 0;
        l = r = i;
    }

};

seg combine(seg a, seg b) {
    seg ans;
    ans.l = a.l; ans.r = b.r;
    ans.set(INF);
    for (int u = 0; u < k; u ++) for (int v = 0; v < k; v ++) {
        int cur = a.r * k + v;
        for (pii nxt: d[cur]) {
            ll w = nxt.nd, node = nxt.st % k;
            for (int x = 0; x < k; x ++) {
                ans.f[u][x] = min(ans.f[u][x], a.f[u][v] + b.f[node][x] + w);
            }
        }
    }

    return ans;
}

seg sec[N], ind[N];
int L[N], R[N];

ll query(int u, int v) {
    int l = u / k, r = v / k;
    if (l >= r) return -1;

    seg ans = ind[l];


    int idL = l / block, idR = r / block;
    if (idL == idR) {
        for (int i = l + 1; i <= r; i ++)
            ans = combine(ans, ind[i]);

        return ans.f[u % k][v % k];
    }

    for (int i = l + 1; i <= R[idL]; i ++) 
        ans = combine(ans, ind[i]);
    for (int i = idL + 1; i < idR; i ++)
        ans = combine(ans, sec[i]);
    for (int i = L[idR]; i <= r; i ++)
        ans = combine(ans, ind[i]);
    
    return ans.f[u % k][v % k];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    // #endif
    
    cin >> k >> n >> m >> q;

    for (int i = 1, u, v, t; i <= m; i ++) {
        cin >> u >> v >> t;
        d[u].push_back({v, t});
    }

    memset(L, -1, sizeof L);
    memset(R, -1, sizeof R);

    for (int i = 0; i <= n / k; i ++) {
        ind[i].init(i);
        R[i / block] = i;
        if (L[i / block] == -1) L[i / block] = i;
    }

    int m = n / k;
    for (int i = 0; i <= m / block; i ++) 
        sec[i] = ind[L[i]];
    
    for (int i = 0; i <= m; i ++) {
        if (i != L[i / block]) 
            sec[i / block] = combine(sec[i / block], ind[i]);
    }

    int u, v;

    auto fix = [&] (ll x) {
        if (x >= 1e15) return -1ll;
        return x;
    };
 
    while (q --) {
        cin >> u >> v;
        cout << fix(query(u, v)) << '\n';
    }

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/

Compilation message (stderr)

toll.cpp:125:9: warning: "/*" within comment [-Wcomment]
  125 | /**  /\_/\
      |

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