oj.uz

Submission #915750

# Submission time Handle Problem Language Result Execution time Memory
915750 2024-01-24T16:17:33 Z asdasdqwer Toll (BOI17_toll) C++14
0 / 100
 253 ms 51284 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii pair<int, int>
const int INF = 1e12;

signed main() {
    int k,n,m,o;cin>>k>>n>>m>>o;
    int cl=(int)ceil(n/k);
    vector<vector<vector<vector<int>>>> lft(cl, vector<vector<vector<int>>>(k, vector<vector<int>>(17, vector<int>(k, INF))));

    for (int i=0;i<m;i++) {
        int a,b,t;cin>>a>>b>>t;
        lft[a/k][a%k][0][b%k]=t;
    }

    for (int j=1;j<17;j++) {
        for (int i=0;i<cl;i++) {
            if (i + (1<<j) >= cl)continue;
            for (int t=0;t<k;t++) {
                for (int md=0;md<k;md++) {
                    for (int tr=0;tr<k;tr++) {
                        lft[i][t][j][tr] = min(lft[i][t][j][tr], lft[i][t][j-1][md] + lft[i+(1<<(j-1))][md][j-1][tr]);
                    }
                }
            }
        }
    }

    while (o--) {
        int a,b;cin>>a>>b;
        
        if (a == b) {
            cout<<0<<"\n";
            continue;
        }

        if (a>b || (a/5 == b/5)) {
            cout<<"-1\n";
            continue;
        }

        int rw = a/k, co=a%k;
        int steps = (b/k) - (a/k);
        vector<int> jmp(k);
        for (int i=0;i<k;i++) {
            jmp[i] = lft[rw][co][0][i];
        }

        steps--;
        rw++;

        int cnt=0;
        while (steps) {
            if ((steps&1)==1) {
                vector<int> tmpjmp(k, INF);
                for (int i=0;i<k;i++) {
                    // use i as a starting point

                    for (int j=0;j<k;j++) {
                        // use j as an ending point
                        tmpjmp[j] = min(tmpjmp[j], jmp[i] + lft[rw][i][cnt][j]);
                    }
                }

                jmp = tmpjmp;
                rw+=(1<<cnt);
            }

            steps>>=1;
            cnt++;
        }

        if (jmp[b%k] >= INF) {
            cout<<-1<<"\n";
            continue;
        }

        cout<<jmp[b%k]<<"\n";
    }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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