제출 #1194713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194713		Hamed_Ghaffari	Toll (BOI17_toll)	C++20	7 / 100	3093 ms	29000 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);
    }
};

node *seg[MXN<<2];

node *merge(node *x, node *y) {
    node *z = new node();
    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) {
        seg[id] = new node();
        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 seg[0];
    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});
    }
    seg[0] = new node();
    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