oj.uz

Submission #1018658

# Submission time Handle Problem Language Result Execution time Memory
1018658 2024-07-10T07:56:13 Z dosts Toll (BOI17_toll) C++17
0 / 100
 79 ms 159100 KB 
//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.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 159100 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 39596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 159100 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -