제출 #1145710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145710		nrg_studio	Toll (BOI17_toll)	C++20	0 / 100	83 ms	73792 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 = 15, MAX_K = 5;
int dist[MAX_N][MAX_K][l2d][MAX_K];

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] = 1e9;}
    F0R(i,m) {
        int a, b, t; cin >> a >> b >> t;
        dist[a/k][a%k][0][b%k] = t;
    }
    int p2 = 2;
    FOR(p,1,l2d) {
        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]);
            }
        } p2 *= 2;
    }
    //cout << dist[1][2][2][2] << '\n';
    while (o--) {
        int a, b; cin >> a >> b;
        int d = max(0,b/k-a/k);

        v<int> ans(5,1e9);
        ans[a%k] = 0;
        a /= k;

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

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