Submission #1176374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176374		minhpk	Toll (BOI17_toll)	C++20	0 / 100	62 ms	25920 KiB

toll

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

const ll INF = 1e13;
ll z[100005][5][5];  // Ma trận chuyển tiếp của từng block
vector<vector<ll>> f[400005];  // Cây phân đoạn: mỗi node lưu ma trận k x k
vector<vector<ll>> full;       // Ma trận "vô cực" dùng khi truy vấn ngoài phạm vi

// Hàm combine: nhân ma trận chuyển tiếp với công thức:
// res[i][j] = min_{l=0}^{k-1} { left[i][l] + right[l][j] }
vector<vector<ll>> combine(vector<vector<ll>> left, vector<vector<ll>> right) {
    vector<vector<ll>> res((int)left.size(), vector<ll>(left.size(), INF));
    for (int i = 0; i < (int)left.size(); i++) {
        for (int j = 0; j < (int)left.size(); j++) {
            for (int l = 0; l < (int)left.size(); l++) {
                res[i][j] = min(res[i][j], left[i][l] + right[l][j]);
            }
        }
    }
    return res;
}

// Xây dựng cây phân đoạn trên các block từ l đến r
void build(int id, int l, int r, int k) {
    f[id].resize(k, vector<ll>(k, INF));
    if (l == r) {
        // Nạp ma trận của block l từ mảng z
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                f[id][i][j] = z[l][i][j];
            }
        }
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid, k);
    build(id * 2 + 1, mid + 1, r, k);
    f[id] = combine(f[id * 2], f[id * 2 + 1]);
}

// Hàm truy vấn trên cây phân đoạn: trả về ma trận chuyển tiếp tổng hợp cho block [x, y]
vector<vector<ll>> get(int id, int l, int r, int x, int y, int k) {
    if (x > r || y < l) {
        return full;
    }
    if (x <= l && r <= y) {
        return f[id];
    }
    int mid = (l + r) / 2;
    vector<vector<ll>> leftRes = get(id * 2, l, mid, x, y, k);
    vector<vector<ll>> rightRes = get(id * 2 + 1, mid + 1, r, x, y, k);
    if (leftRes == full) return rightRes;
    if (rightRes == full) return leftRes;
    return combine(leftRes, rightRes);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int k, a, b, c;
    cin >> k >> a >> b >> c;
    
    // Khởi tạo mảng z: gán giá trị INF cho mọi vị trí
    for (int i = 0; i < 10005; i++){
        for (int j = 0; j < k; j++){
            for (int t = 0; t < k; t++){
                z[i][j][t] = INF;
            }
        }
    }
    
    // Nhập các cạnh: với mỗi cạnh từ đỉnh x đến đỉnh y có trọng số t,
    // ánh xạ vào block: x/k là chỉ số block, x%k là chỉ số trong block
    for (int i = 1; i <= b; i++){
        int x, y, t;
        cin >> x >> y >> t;
        z[x / k][x % k][y % k] = t;
    }
    
    // Tính số block: làm tròn lên, tức:
    // n = ceil(a/k) = (a + k - 1) / k.
    int n = (a + k - 1) / k;
    
    // Khởi tạo ma trận full (vô cực) với kích thước k x k
    full.resize(k, vector<ll>(k, INF));
    
    // Xây dựng cây phân đoạn trên các block từ 0 đến n-1
    build(1, 0, n - 1, k);
    
    // Xử lý truy vấn
    while(c--){
        int x, y;
        cin >> x >> y;
        int sta = x / k;
        int fin = y / k;
        // Nếu nguồn và đích nằm trong cùng một block, theo quy định in -1
        if (sta == fin) {
            cout << -1 << "\n";
            continue;
        }
        // Truy vấn trên các block từ sta đến fin-1
        vector<vector<ll>> res = get(1, 0, n - 1, sta, fin - 1, k);
        if (res == full || res[x % k][y % k] >= INF) {
            cout << -1 << "\n";
        } else {
            cout << res[x % k][y % k] << "\n";
        }
    }
    
    return 0;
}

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