Submission #1344681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344681		Aquarius	Toll (BOI17_toll)	C++20	100 / 100	76 ms	30496 KiB

toll

#include<bits/stdc++.h>
#define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

const int INF = 1e15;
const int MAXK = 5;
int k, n, m, q;


struct Infor {
    int u, v, id;
};

struct Matrix {
    int data[MAXK][MAXK];

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

    Matrix() {
        for(int i=0; i<MAXK; i++)
            for(int j=0; j<MAXK; j++) data[i][j] = INF;
    }
};

Matrix operator * (Matrix a, Matrix b) {
    Matrix res;
    for(int i=0; i<MAXK; i++) {
        for(int j=0; j<MAXK; j++) {
            for(int k=0; k<MAXK; k++) {
                res[i][j] = min(res[i][j], a[i][k] + b[k][j]);
            }
        }
    }
    return res;
}

const int N = 5e4+4;
const int MAXQ = 1e5+5;
int ans[MAXQ];
Matrix a[N];
Matrix suff[N], pref[N];

void cdq(int l, int r, vector<Infor> &query) {
    if(l == r) {
        for(Infor &tmp: query) {
            int u = tmp.u;
            int v = tmp.v;
            int id = tmp.id;
            int ql = u/k;
            int qr = v/k - 1;
            if(ql == l && qr == l) {
                ans[id] = a[l][u%k][v%k];
                if(ans[id] >= INF) ans[id] = -1;
            } else {
                ans[id] = -1;
            }
        }
        return;
    }

    int mid = l + r >> 1;
    for(int i = mid; i>=l; i--) {
        if(i == mid) suff[i] = a[i];
        else suff[i] = a[i]*suff[i+1];

    }

    for(int i=mid+1; i<=r; i++) {
        if(i == mid+1) pref[i] = a[i];
        else pref[i] = pref[i-1]*a[i];
    }


    vector<Infor> query_left, query_right;
    for(Infor &tmp: query) {
        int u = tmp.u;
        int v = tmp.v;
        int id = tmp.id;
        int ql = u/k;
        int qr = v/k -1;
        if(qr <= mid) query_left.push_back(tmp);
        else if(ql >=mid+1) query_right.push_back(tmp);
        else {
            Matrix res = suff[ql]*pref[qr];
            ans[id] = res[u%k][v%k];
            if(ans[id] >= INF) ans[id] = -1;
        }
    }
    cdq(l, mid, query_left);
    cdq(mid+1, r, query_right);

}

void solve() {
    cin >> k >> n >> m >> q;
    for(int i=1; i<=m; i++) {
        int u, v, t; cin >> u >> v >> t;
        a[u/k][u%k][v%k] = t;
    }


    vector<Infor> query;
    for(int i=1; i<=q; i++) {
        int u, v; cin >>u >> v;
        query.push_back({u, v, i});
    }

    cdq(0, n/k, query);
    for(int i=1; i<=q; i++) cout << ans[i] <<'\n';
}
signed main() {
    if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--) solve();
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:116:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
      |                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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