Submission #1145757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145757		nrg_studio	Toll (BOI17_toll)	C++20	100 / 100	173 ms	78716 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

const int MAX_N = 50000, l2d = 16, MAX_K = 5;
int dist[MAX_N][MAX_K][l2d][MAX_K];
int INF = 1e9;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m, k, o; cin >> k >> n >> m >> o;

    F0R(i,n) F0R(j,k) F0R(l,l2d) F0R(z,k) {dist[i][j][l][z] = INF;}
    F0R(i,m) {
        int a, b, t; cin >> a >> b >> t;
        dist[a/k][a%k][0][b%k] = t;
    }
    for(int p=1,p2=2;p<l2d;p++,p2*=2) {
        F0R(i,n-p2) {
            F0R(start,k) F0R(mid,k) F0R(stop,k) {
                chmin(dist[i][start][p][stop],
                    dist[i][start][p-1][mid]+dist[i+p2/2][mid][p-1][stop]);
            }
        }
    }
    //cout << dist[4][0][0][0] << 'e'<<'\n';
    
    while (o--) {
        int a, b; cin >> a >> b;
        int d = b/k-a/k;

        v<int> ans(k,INF);

        ans[a%k] = 0;
        a /= k;

        for (int b=0,p=1;b<l2d;b++,p*=2) {
            if (d&(1<<b)) {
                v<int> nxt(k,INF);
                F0R(i,k) {
                    F0R(j,k) {
                        chmin(nxt[j],ans[i]+dist[a][i][b][j]);
                    }
                }
                ans = nxt;
                a += p;
            }
        }
        
        cout << (ans[b%k]==INF ? -1 : ans[b%k]) << '\n';
    }
}

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