Submission #944209

#	Time	Username	Problem	Language	Result	Execution time	Memory
944209		AlphaMale06	Toll (BOI17_toll)	C++17	100 / 100	170 ms	81124 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define pb push_back

const int N = 5e4+2;
const int inf = 1e9;

int k, n, b;

vector<vector<int>> mat[N][16];

vector<int> mul(vector<int> & f, vector<vector<int>> & s){
    vector<int> ret(k, inf);
    for(int i=0; i<k;i++){
        for(int j=0; j<k; j++){
            ret[i]=min(ret[i], f[j]+s[j][i]);
        }
    }
    return ret;
}

vector<vector<int>> mul(vector<vector<int>> & f, vector<vector<int>> & s){
    vector<vector<int>> ret;
    for(int i=0; i<k; i++)ret.pb(mul(f[i], s));
    return ret;
}

void smin(int & f, int s){
    if(s<f)f=s;
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m, q;
    cin >> k >> n >> m >> q;
    b=(n+k-1)/k;
    for(int j=0; j<16; j++){
        for(int i=0; i+(1<<j)<=b; i++){
            mat[i][j].resize(k);
            for(int l=0; l<k; l++)mat[i][j][l].resize(k, inf);
        }
    }
    for(int i=0; i< m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        smin(mat[x/k][0][x%k][y%k], c);
    }
    for(int j=1; j<16; j++){
        for(int i=0; i+(1<<j)<=b; i++){
            mat[i][j]=mul(mat[i][j-1], mat[i+(1<<(j-1))][j-1]);  
        }
    }
    while(q--){
        int l, r;
        cin >> l >> r;
        if(l==r){
            cout << 0 << '\n';
            continue;
        }
        int ly = l/k;
        int ry = r/k;
        if(ly>=ry){
            cout << -1 << '\n';
            continue;
        }
        vector<int> st(k, inf);
        st[l%k]=0;
        int str=ly;
        for(int i=15; i>=0; i--){
            if(ly+(1<<i)<=ry){
                st=mul(st, mat[ly][i]);
                ly+=(1<<i);
            }   
        }
        if(st[r%k]>=inf)cout << -1 << '\n';
        else cout << st[r%k] << '\n';
    }
    
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:75:13: warning: unused variable 'str' [-Wunused-variable]
   75 |         int str=ly;
      |             ^~~

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