Submission #1239102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239102		thuhienne	Toll (BOI17_toll)	C++20	100 / 100	67 ms	25964 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define MULTEST int t;cin >> t;while (t--) solve();
#define rf(__abc__) freopen(__abc__".inp","r",stdin);freopen(__abc__".out","w",stdout);

const int mod = 1e9 + 7;

long long pw(long long x,long long y) {
    if (y == 0) return 1;
    if (y % 2 == 0) {
        long long a = pw(x,y/2);
        return a*a%mod;
    } else {
        long long a = pw(x,y - 1);
        return a*x%mod;
    }
}

int add(int x,int y) {
    x += y;
    if (x >= mod) x -= mod;
    return x;
}

int subtract(int x,int y) {
    x -= y;
    if (x < 0) x += mod;
    return x;
}

int mul(long long x,int y) {
    x *= y;
    if (x >= mod) x %= mod;
    return x;
}

///Code goes here

struct matrix {
    long long data[5][5];
    int row,col;
    matrix () {

    }
    matrix (int r,int c) {
        row = r,col = c;
        for (int i = 0;i < row;i++) for (int j = 0;j < col;j++) data[i][j] = 0;
    }
    matrix operator * (const matrix & b) {
        matrix a = *this;
        matrix c(a.row,b.col);
        for (int i = 0;i < a.row;i++) {
            for (int j = 0;j < b.col;j++) {
                c.data[i][j] = mod;
                for (int k = 0;k < a.col;k++) {
                    c.data[i][j] = min(c.data[i][j],a.data[i][k] + b.data[k][j]);
                }
            }
        }
        return c;
    }
};

matrix mat[50009];
//order:left -> right

int k,n,m,q;
vector <pair<int,int>> adj[50009];

struct query {
    int l,r,index;
} ask[10009];

matrix answer[10009];

matrix acc[50009];
void dnc(int l,int r,vector <query> & bruh) {
    if (l == r) {
        for (auto x : bruh) {
            answer[x.index] = mat[l];
        }
        return;
    }
    int mid = (l + r) >> 1;
    acc[mid] = mat[mid];
    acc[mid + 1] = mat[mid + 1];
    for (int i = mid - 1;i >= l;i--) {
        acc[i] = mat[i] * acc[i + 1];
    }
    for (int i = mid + 2;i <= r;i++) {
        acc[i] = acc[i - 1] * mat[i];
    }
    vector <query> left,right;
    for (auto x : bruh) {
        if (x.l > mid) right.push_back(x);
        else if (x.r <= mid) left.push_back(x);
        else answer[x.index] = acc[x.l] * acc[x.r];
    }
    dnc(l,mid,left);
    left.clear();
    dnc(mid + 1,r,right);
    right.clear();
}

int main() {
    //rf("");
    FastIO
    //MULTEST

    cin >> k >> n >> m >> q;
    n = (n + k - 1)/k*k;
    for (int i = 1;i <= m;i++) {
        int u,v,w;cin >> u >> v >> w;
        adj[v].push_back({u,w});
    }

    for (int i = 0;i * k <= n;i++) {
        //i*k,i*k + 1,...,i*k + k - 1
        ///init
        for (int d = 0;d < k;d++) {
            for (int b = 0;b < k;b++) {
                mat[i].data[d][b] = 0;
            }
        }
        mat[i].row = mat[i].col = k;
        ///create min-plus matrix
        for (int node = i*k;node <= i*k + k - 1;node++) {
            for (auto c : adj[node]) {
                int child = c.first,cost = c.second;
                mat[i].data[child%k][node%k] = cost;
            }
        }
        ///fill in missing value
        for (int d = 0;d < k;d++) {
            for (int b = 0;b < k;b++) {
                if (!mat[i].data[d][b]) mat[i].data[d][b] = mod;
            }
        }
    }
    vector <query> allquery;
    for (int i = 1;i <= q;i++) {
        int l,r;cin >> l >> r;
        ask[i] = {l,r,i};
        if (l/k != r/k) allquery.push_back({l/k + 1,r/k,i});
    }
    dnc(1,n,allquery);
    for (int i = 1;i <= q;i++) {
        if (ask[i].l/k == ask[i].r/k) cout << -1 << '\n';
        else cout << (answer[i].data[ask[i].l%k][ask[i].r%k] >= 1e9 ? -1 : answer[i].data[ask[i].l%k][ask[i].r%k]) << '\n';
    }

    return 0;
}

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