Submission #856541

#	Time	Username	Problem	Language	Result	Execution time	Memory
856541		anton	Toll (BOI17_toll)	C++17	100 / 100	172 ms	197076 KiB

toll

#include<bits/stdc++.h>

using namespace std;
#define int long long

const int INF = 1e18;
const int MAX_K = 10;
int K;

struct M{
    int dist[MAX_K][MAX_K];
    M(){
        for(int i = 0; i<K; i++){
            for(int j = 0; j<K; j++){
                dist[i][j] = INF;
            }
        }
    }

    void sh(){
        /*for(int i = 0; i<K; i++){
            for(int j=0; j<K; j++){
                cout<<dist[i][j]<<" ";
            }
            cout<<endl;
        }

        cout<<endl;*/
    }
};

M e(){
    M res;

    for(int i= 0; i<K; i++){
        for(int j = 0; j<K; j++){
            if(i==j){
                res.dist[i][j] = 0;
            }
            else{
                res.dist[i][j] = INF;
            }
        }
    }
    return res;
}

M combine(M& lh, M&rh){
    M res;
    for(int mid=  0; mid<K; mid++){
        for(int a = 0; a<K; a++){
            for(int b = 0; b<K; b++){
                res.dist[a][b] = min(res.dist[a][b], lh.dist[a][mid] + rh.dist[mid][b]);
            }
        }
    }
    return res;
}

struct Tree{
    vector<M> tree;

    void build(vector<M>& v, int lt, int rt, int t){
        if(lt == rt){
            tree[t] = v[lt];
        }
        else{
            int mid = (lt+rt)/2;
            build(v, lt, mid, t*2);
            build(v, mid+1, rt, t*2+1);
            tree[t] = combine(tree[t*2], tree[t*2+1]);
        }
        //cout<<"lt "<<lt<<" rt "<<rt<<endl;
        tree[t].sh();
    }

    M get(int l, int r, int lt, int rt, int t){
        if(r<lt || rt<l){
            return e();
        }
        else if(l<=lt && rt<=r){
            return tree[t];
        }
        else{
            int mid = (lt+rt)/2;

            M lh = get(l, r, lt, mid, t*2);
            M rh = get(l, r, mid+1, rt, t*2+1);
            return combine(lh, rh);
        }
    }

    void sh(){
        
    }
};

signed main(){
    int n, m, o;

    cin>>K>>n>>m>>o;

    int l = (n+K-2)/K;

    vector<M> v(l);

    for(int i = 0; i<m; i++){
        int a,b, t;
        cin>>a>>b>>t;

        //cout<<"a is "<<a<<endl;
        v[a/K].dist[a%K][b%K] = t;
    }

    Tree tr;
    tr.tree.resize(4*l +1);
    tr.build(v, 0, l-1, 1);

    tr.sh();


    for(int i = 0; i<o; i++){
        int a, b;
        cin>>a>>b;

        int res = tr.get(a/K, (b/K)-1, 0, l-1, 1).dist[a%K][b%K];
        if(res==INF){
            cout<<-1<<endl;
        }
        else{
            cout<<res<<endl;
        }
    }
}

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