Submission #1128516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128516		Kerim	Toll (BOI17_toll)	C++20	100 / 100	103 ms	24952 KiB

toll

#include "bits/stdc++.h"

using namespace std;
const int N = 5e4+5;
const int K = 5;
const int INF = 1e9;
    int k, n, m, q;
struct node{
    int m[K][K];
    node(){//constructor
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                m[i][j] = INF;
    }
    void set(node other){
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                m[i][j] = other.m[i][j];
    }
    void print(){
        for (int i = 0; i < k; i++){
            for (int j = 0; j < k; j++)
                printf("%d ", m[i][j]);
            puts("");
        }
        puts("");
    }
}edge[N], s[N<<2], I;

node merge(node A, node B){
    node C;
    for (int x = 0; x < K; x++)
        for (int y = 0; y < K; y++)
            for (int z = 0; z < K; z++)
                C.m[x][z] = min(C.m[x][z], A.m[x][y] + B.m[y][z]);
    return C;
}
void build(int nd, int x, int y){
    if (x + 1 == y){
        s[nd].set(edge[x]);
        return;
    }
    int mid = (x+y) >> 1;
    build(nd<<1, x, mid);
    build(nd<<1|1, mid, y);
    s[nd] = merge(s[nd<<1], s[nd<<1|1]);
}
node get(int l, int r, int nd, int x, int y){
    // cout<<l<<" "<<r<<" "<<nd<<" "<<x<<" "<<y<<endl;
    if (l >= y or x >= r)
        return I;
    if (l <= x and y <= r){
        // s[nd].print();
        return s[nd];
    }
    int mid = (x+y) >> 1;
    node A = get(l, r, nd<<1, x, mid);
    node B = get(l, r, nd<<1|1, mid, y);
    return merge(A, B);
}

int main(){
    for (int i = 0; i < K; i++)
        I.m[i][i] = 0;
    // freopen("file.in", "r", stdin);
    scanf("%d%d%d%d", &k, &n, &m, &q);
    for (int i = 0; i < m; i++){
        int a, b, t;
        scanf("%d%d%d", &a, &b, &t);
        edge[a/k].m[a%k][b%k] = t;
    }
    build(1, 0, (n-1)/k);
    while (q--){
        int a, b;
        scanf("%d%d", &a, &b);
        if (b/k <= a/k){
            puts("-1");
            continue;
        }
        // cout<<a/k<<" "<<b/k<<" "<<a%k<<" "<<b%k<<endl;
        node result = get(a/k, b/k, 1, 0, (n-1)/k);
        if (result.m[a%k][b%k] >= 1e9)
            result.m[a%k][b%k] = -1;
        // result.print();
        printf("%d\n", result.m[a%k][b%k]);
    }
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d%d%d%d", &k, &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d%d%d", &a, &b, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

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