Submission #1287720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287720		G_thang_dizz_lenhi	Toll (BOI17_toll)	C++17	100 / 100	125 ms	157100 KiB

toll

#include<bits/stdc++.h>
typedef int ii;
typedef long long ll;

using namespace std;

const string name = "";
const ii MOD = 1e9 + 7;
const ii N = 5e4 + 10;
const ii M = 16;


ii k, n, m, q;

struct Matrix{
    ll d[5][5];

    Matrix(){
        memset(d, 0x3f, sizeof d);
    }

    auto & operator [] (int i) { return d[i]; }

    const auto & operator[] (int i) const { return d[i];}


    Matrix operator + (const Matrix &b) {
        Matrix a = *this;

        Matrix c;
        for (ii i = 0;i < k;i++){
            for (ii j = 0;j < k;j++){
                for (ii l = 0;l < k;l++){
                    c[i][j] = min(c[i][j], a[i][l] + b[l][j]);
                }
            }
        }
        return c;
    }

    void print(){
        cerr << "---------\n";
        for (ii i = 0;i < k;i++){
            for (ii j = 0;j < k;j++){
                cerr << (d[i][j] != 0x3f3f3f3f3f3f3f3f ? d[i][j] : 0) << " ";
            }
            cerr << endl;
        }
        cerr << "---------\n";
    }
};

Matrix d[M][N];


void INP(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen((name + ".inp").c_str(),"r")){
        freopen((name + ".inp").c_str(),"r",stdin);
//        freopen((name + ".out").c_str(),"w",stdout);
    }
    cin >> k >> n >> m >> q;
    n = n / k;
    ii a, b, t;
    while(m--){
        cin >> a >> b >> t;
        d[0][a / k][a % k][b % k] = t;
    }
}

void build(){
    for (ii bit = 1;bit < M;bit++){
        for (ii i = 0;i + (1 << bit) <= n;i++){
            d[bit][i] = d[bit - 1][i] + d[bit - 1][i + (1 << bit - 1)];
        }
    }
}

Matrix get(ii st, ii sz){
    Matrix res;
    bool ok = true;
    for (ii bit = M - 1;bit >= 0;bit--){
        if ((1 << bit) <= sz){
            if (!ok)
            res = res + d[bit][st];
            else res = d[bit][st], ok = false;
            sz -= (1 << bit);
            st += (1 << bit);
        }
    }
    return res;
}

int main(){
    INP();
    build();
    ii u, v;
    Matrix T = d[1][0];
//    T.print();

    while(q--){
        cin >> u >> v;
        T = get(u / k, (v / k) - (u / k));
        if (T[u % k][v % k] == 0x3f3f3f3f3f3f3f3f){
            cout << -1 << "\n";
        }
        else{
            cout << T[u % k][v % k] << "\n";
        }
    }
    return 0;
}

//NGT 1600-2000 cf
//1/200 hard quests

Compilation message (stderr)

toll.cpp: In function 'void INP()':
toll.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen((name + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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