Submission #1176371

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

toll

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

int k, a, b, c;
int bruh = 1e13;
int z[100005][5][5]; // Ma trận chuyển tiếp của từng block
vector<vector<int>> f[400005];

// Hàm combine: nhân ma trận (điều kiện: các ma trận có kích thước k x k)
vector<vector<int>> combine(vector<vector<int>> left, vector<vector<int>> right) {
    vector<vector<int>> res(k, vector<int>(k, bruh));
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            for (int l = 0; l < k; 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 (các chỉ số của block)
void build(int id, int l, int r) {
    f[id].resize(k, vector<int>(k, bruh));
    if (l == r) {
        // Nạp trực tiếp ma trận của block l
        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);
    build(id * 2 + 1, mid + 1, r);
    f[id] = combine(f[id * 2], f[id * 2 + 1]);
}

// Ma trận “vô cực” dùng để đánh dấu các phần tử không hợp lệ trong truy vấn
vector<vector<int>> full;

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> k >> a >> b >> c;

    // Khởi tạo mảng z với giá trị bruh cho mọi block và 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] = bruh;
            }
        }
    }

    // Nhập các cạnh (edge) – ánh xạ theo block
    // Với mỗi cạnh từ đỉnh x đến đỉnh y với trọng số t, ta gán:
    //     z[x/k][x%k][y%k] = t;
    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: dùng công thức làm tròn lên
    int n = (a + k - 1) / k;
    // Khởi tạo ma trận "full" (vô cực) dùng trong truy vấn
    full.resize(k, vector<int>(k, bruh));

    // Xây dựng cây phân đoạn trên các block [0, n-1]
    build(1, 0, n - 1);

    // Xử lý truy vấn
    for (int i = 1; i <= c; i++) {
        int x, y;
        cin >> x >> y;
        int sta = x / k, fin = y / k;
        // Nếu nguồn và đích nằm trong cùng một block thì theo quy định không có đường đi hợp lệ
        if (sta == fin) {
            cout << -1 << "\n";
            continue;
        }
        // Truy vấn trên các block từ sta đến fin-1
        vector<vector<int>> r = get(1, 0, n - 1, sta, fin - 1);
        // Kiểm tra nếu không có đường đi hoặc giá trị kết quả vượt ngưỡng bruh
        if (r == full || r[x % k][y % k] >= bruh) {
            cout << -1 << "\n";
        } else {
            cout << r[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