제출 #1135098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135098		a5a7	Toll (BOI17_toll)	C++20	100 / 100	205 ms	75580 KiB

toll

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

struct Matrix{
    int n;
    vector<vector<ll>> v;
    Matrix(){}
    Matrix(int n) : n(n) {
        v = vector<vector<ll>>(n, vector<ll>(n, -1));
    }
    Matrix operator*(Matrix x){
        Matrix y(n);
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k < n; k++){
                    if (v[i][j] == -1) continue;
                    if (x.v[j][k] == -1) continue;
                    y.v[i][k] = y.v[i][k] == -1 ? v[i][j]+x.v[j][k] : min(y.v[i][k], v[i][j]+x.v[j][k]);
                }
            }
        }
        return y;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, n, m, o; cin >> k >> n >> m >> o;
    int cmp = (n+k-1)/k;
    Matrix up[cmp][16];
    for (int i = 0; i < cmp; i++){
        for (int j = 0; j < 16; j++){
            up[i][j] = Matrix(k);
        }
    }
    for (int i = 0; i < m; i++){
        int a, b, t; cin >> a >> b >> t;
        up[a/k][0].v[a%k][b%k] = t;
    }
    for (int i = 1; i < 16; i++){
        for (int j = 0; j < cmp; j++){
            if ((j+(1<<(i-1))) >= cmp) continue;
            up[j][i] = up[j][i-1]*up[j+(1<<(i-1))][i-1];
        }
    }
    for (int i = 0; i < o; i++){
        int a, b; cin >> a >> b;
        if ((a/k) > (b/k)){
            cout << -1 << endl; continue;
        }else if ((a/k) == (b/k)){
            cout << (a==b ? 0 : -1) << endl;
        }else{
            int curr = (a/k);
            Matrix ans(k);
            for (int i = 0; i < k; i++) ans.v[i][i] = 0;
            for (int i = 0; i < 16; i++){
                if ((1<<i)&((b/k)-(a/k))) ans = ans*up[curr][i], curr += 1<<i;
            }
            cout << ans.v[a%k][b%k] << endl;
        }
    }
}

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