Submission #1018658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018658		dosts	Toll (BOI17_toll)	C++17	0 / 100	79 ms	159100 KiB

toll

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;
const int N = 5e4,inf = 2e9,K = 5; 

int k,n,m,o;

struct Matrix {
    int c[K][K];

    Matrix() {
        for (int i=0;i<k;i++) {
            for (int j=0;j<k;j++) c[i][j] = inf;
        }
    }
};

Matrix up[N][16];


Matrix merge(const Matrix& m1,const Matrix& m2) {
    Matrix r;
    for (int i=0;i<k;i++) {
        for (int j=0;j<k;j++) {
            for (int jj=0;jj<k;jj++) {
                r.c[i][j] = min(r.c[i][j],m1.c[i][jj]+m2.c[jj][j]);
            }
        }
    }
    return r;
}

void solve() {
    cin >> k >> n >> m >> o;
    for (int i=0;i<=n/k;i++) for (int j=0;j<16;j++) up[i][j] = Matrix();

    for (int i=1;i<=m;i++) {
        int a,b,t;
        cin >> a >> b >> t;
        up[a/k][0].c[a%k][b%k] = t;
    }
    for (int i=1;i<16;i++) {
        for (int j=0;j+(1<<(i-1))<n/k;j++) {
            up[j][i] = merge(up[j][i-1],up[j+(1<<(i-1))][i-1]);
        }
    }
    while (o--) {
        int a,b;
        cin >> a >> b;
        if (a/k == b/k) {
            cout << ((a == b) ? 0 : -1) <<  endl;
            continue;
        }
        int l1 = a/k,l2 = b/k;
        Matrix M = up[l1][0];
        l1++;
        for (int i=15;i>=0;i--) {
            if (l1+(1<<i) <= l2) {
                M = merge(M,up[l1][i]);
                l1+=(1<<i);
            }
        }
        cout << (M.c[a%k][b%k] == inf ? -1 : M.c[a%k][b%k]) << '\n';
    }
}  
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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