oj.uz

Submission #915783

# Submission time Handle Problem Language Result Execution time Memory
915783 2024-01-24T17:18:10 Z asdasdqwer Toll (BOI17_toll) C++14
15 / 100
 277 ms 51664 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
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)break;
            
            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/k == b/k)) {
            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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 50388 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 3 ms 1368 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 149 ms 51028 KB Output is correct
9 Correct 158 ms 51056 KB Output is correct
10 Correct 103 ms 50256 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 2 ms 1376 KB Output is correct
7 Correct 2 ms 1376 KB Output is correct
8 Correct 4 ms 1632 KB Output is correct
9 Correct 3 ms 1632 KB Output is correct
10 Correct 114 ms 50776 KB Output is correct
11 Correct 208 ms 51032 KB Output is correct
12 Correct 236 ms 51272 KB Output is correct
13 Correct 255 ms 51512 KB Output is correct
14 Correct 216 ms 50768 KB Output is correct
15 Correct 129 ms 38484 KB Output is correct
16 Correct 140 ms 38716 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 2 ms 1376 KB Output is correct
7 Correct 2 ms 1376 KB Output is correct
8 Correct 4 ms 1632 KB Output is correct
9 Correct 3 ms 1632 KB Output is correct
10 Correct 114 ms 50776 KB Output is correct
11 Correct 208 ms 51032 KB Output is correct
12 Correct 236 ms 51272 KB Output is correct
13 Correct 255 ms 51512 KB Output is correct
14 Correct 216 ms 50768 KB Output is correct
15 Correct 129 ms 38484 KB Output is correct
16 Correct 140 ms 38716 KB Output is correct
17 Correct 215 ms 51028 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 444 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 8 ms 1628 KB Output is correct
24 Correct 7 ms 1372 KB Output is correct
25 Correct 9 ms 1744 KB Output is correct
26 Correct 8 ms 1628 KB Output is correct
27 Correct 122 ms 50940 KB Output is correct
28 Correct 257 ms 51276 KB Output is correct
29 Incorrect 277 ms 51664 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 50388 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 3 ms 1368 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 149 ms 51028 KB Output is correct
9 Correct 158 ms 51056 KB Output is correct
10 Correct 103 ms 50256 KB Output is correct
11 Correct 260 ms 49552 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Incorrect 0 ms 352 KB Output isn't correct
15 Halted 0 ms 0 KB -