Submission #953771

#	Time	Username	Problem	Language	Result	Execution time	Memory
953771		infrapolar	Toll (BOI17_toll)	C++17	100 / 100	115 ms	81232 KiB

toll

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct min_matrix{
    int ysize;
    int xsize;
    vector<vector<int>> data;
    min_matrix(){}
    min_matrix(int x, int y, int init) : ysize(y), xsize(x), data(ysize){
        for (auto &i : data)
            i = vector<int>(xsize, init);
    }
    min_matrix operator*(const min_matrix& other) const{
        min_matrix result(other.xsize, ysize, inf);
        for (int from = 0; from < xsize; from++)
        {
            for (int to = 0; to < xsize; to++)
            {
                for (int mid = 0; mid < xsize; mid++)
                {
                    result.data[to][from] = min(result.data[to][from], data[mid][from] + other.data[to][mid]);
                }
                
            }
            
        }
        
        return result;
    }
};
template<class T> 
struct sparse_table
{
    vector<vector<T>> data;
    function<T(const T&, const T&)> op;
    sparse_table(){}
    sparse_table(function<T(const T&, const T&)> op, int sz, T* arr) : op(op){
        data.emplace_back(vector(arr, arr+sz));
        int block_size = 2;
        int j = 1;
        while (block_size < sz){
            data.emplace_back(sz);
            for (int begin = 0; begin < sz; begin+=2*block_size)
            {
                int center = min(sz-1, begin+block_size-1);
                data[j][center] = arr[center];
                for (int i = center - 1; i >= begin; i--)
                {
                    data[j][i] = op(arr[i], data[j][i+1]);
                }
                if (center != sz - 1)
                    data[j][center+1] = arr[center+1];
                for (int i = center+2; i < min(center+block_size+1, sz); i++)
                {
                    data[j][i] = op(data[j][i-1], arr[i]);
                }
                
            }
            block_size *= 2;
            j++;
        }
    }
    min_matrix query(int l, int r){
        if (l == r)
            return data[0][l];
        int layer = -1;
        int t = l ^ r;
        while (t){
            layer++;
            t >>= 1;
        }
        return op(data[layer][l], data[layer][r]);
    }
};
void solve(){
    int k, n, m, q;
    cin >> k >> n >> m >> q;
    vector<min_matrix> data_for_table(n/k, min_matrix(k, k, inf));
    for (int i = 0; i < m; i++)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        data_for_table[a/k].data[b%k][a%k] = cost;
    }
    sparse_table<min_matrix> table([](const min_matrix& l, const min_matrix& r){return l*r;}, data_for_table.size(), data_for_table.data());
    for (int i = 0; i < q; i++)
    {
        int a, b;
        cin >> a >> b;
        if (b/k <= a/k){
            cout << "-1\n";
            continue;
        }
        int result = table.query(a/k, b/k-1).data[b%k][a%k];
        if (result == inf){
            result = -1;
        }
        cout << result << '\n';
    }
    
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int t = 1;
    for (int i = 0; i < t; i++)
    {
        solve();
    }
    
}

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