Submission #1194712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194712		Hamed_Ghaffari	Toll (BOI17_toll)	C++20	7 / 100	3096 ms	22600 KiB

toll

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second
#define mins(a,b) (a = min(a,b))

const int MXN = 5e4+5, MXK = 5, inf=1e9;

int k;

struct node {
    int dis[MXK][MXK];
    node() {
        for(int i=0; i<MXK; i++)
            fill(dis[i], dis[i]+MXK, inf);
    }
} seg[MXN<<2];

node merge(node x, node y) {
    node z;
    for(int i=0; i<k; i++)
        for(int j=0; j<k; j++)
            for(int l=0; l<k; l++)
                mins(z.dis[i][l], x.dis[i][j] + y.dis[j][l]);
    return z;
}

int n;
vector<pii> g[MXN];

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

void build(int l=0, int r=(n-1)/k, int id=1) {
    if(r-l==0) return;
    if(r-l==1) {
        for(int i=l*k; i<(l+1)*k && i<n; i++)
            for(auto [j, w] : g[i])
                mins(seg[id].dis[i%k][j%k], w);
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}

node get(int s, int e, int l=0, int r=(n-1)/k, int id=1) {
    if(r-l==0) return node();
    if(s<=l && r<=e) return seg[id];
    if(e<=mid) return get(s, e, l, mid, lc);
    if(s>=mid) return get(s, e, mid, r, rc);
    return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int m, q;
    cin >> k >> n >> m >> q;
    for(int i=0,u,v,w; i<m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    build();
    while(q--) {
        int a, b;
        cin >> a >> b;
        if(a/k==b/k) cout << "-1\n";
        int ans = get(a/k, b/k).dis[a%k][b%k];
        cout << (ans==inf ? -1 : ans) << '\n';
    }
    return 0;
}

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