Submission #646203

#	Time	Username	Problem	Language	Result	Execution time	Memory
646203		retarddestroyer	Toll (BOI17_toll)	C++14	0 / 100	134 ms	37320 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fors(u, n, s) for(ll u = (s); u<(n); u++)
#define foru(u, n) fors(u, n, 0)

#define N 50000
#define K 5

struct funny_matrix{ /// element i, j is cost of going from i to j
    ll arr[K][K];

    void id_max(){
        foru(i, K) foru(j, K) arr[i][j]=INT_MAX;
    }

    void id_diag(){
        foru(i, K) foru(j, K) arr[i][j]=INT_MAX;
        foru(i, K) arr[i][i]=0;
    }
};

funny_matrix multiply(funny_matrix a, funny_matrix b){ ///going throug a than b
    funny_matrix output;
    output.id_max();

    foru(i, K) foru(j, K){
        foru(k, K){
            output.arr[i][j] = min(output.arr[i][j], a.arr[i][k] + b.arr[k][j]);
        }
    }

    return output;
}

funny_matrix edges[N];

struct seg_tree{
    funny_matrix arr[4*N];

    void construct_ins(int id, int a, int b){ ///a to b inclusive
        if(a==b) {arr[id] = edges[a]; return;}
        int m = (a+b)/2;
        construct_ins(2*id, a, m); construct_ins(2*id+1, m+1, b);
        arr[id] = multiply(arr[2*id], arr[2*id+1]);
    }

    void construct(){
        construct_ins(1, 0, N-1);
    }

    funny_matrix read_ins(int id, int a, int b, int qa, int qb){
        if (a==qa && b==qb) return arr[id];
        int m = (a+b)/2;
        funny_matrix res1;
        funny_matrix res2;
        res1.id_diag(); res2.id_diag();
        if(qa>qb) return res1;
        if(qa<=m) res1 = read_ins(2*id, a, m, qa, min(qb, m));
        if(qb>=m+1) res1 = read_ins(2*id+1, m+1, b, max(qa, m+1), qb);
        return multiply(res1, res2);
    }

    funny_matrix read(int qa, int qb){
        return read_ins(1, 0, N-1, qa, qb);
    }
};

seg_tree tree;

int main()
{
    int k; int n; int m; int o;

    cin >> k >> n >> m >> o;

    foru(i, N) edges[i].id_max();

    foru(_i, m){
        ll a, b, t; cin >> a >> b >> t;
        int l = a/k;
        int a_prim = a%k;
        int b_prim = b%k;
        edges[l].arr[a_prim][b_prim] = min(edges[l].arr[a_prim][b_prim], t);
    }

    tree.construct();

    foru(_i, o){
        int a, b; cin >> a >> b;
        int la = a/k; int lb = b/k;
        int a_prim = a%k; int b_prim = b%k;
        ll res = tree.read(la, lb-1).arr[a_prim][b_prim];
        if(res>=INT_MAX) cout << -1 << endl;
        else cout << res << endl;
    }

    return 0;
}

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