Submission #384607

#	Time	Username	Problem	Language	Result	Execution time	Memory
384607		JerryLiu06	Toll (BOI17_toll)	C++11	100 / 100	192 ms	9708 KiB

toll

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, int> ppi;

#define pb push_back

#define f first
#define s second

int K, N, M, O; vector<pii> adj[50010]; vector<pii> Q;

int DP[50010][5][5]; int ans[100010]; const int INF = 1061109567;

void divide(int L, int R, vector<int> V) {
    if (R < L) return ; int mid = (L + R) / 2;
    
    for (int i = L; i <= R; i++) memset(DP[i], 0x3f, sizeof DP[i]);

    for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) DP[mid][i][j] = (i == j) ? 0 : INF;

    for (int i = mid - 1; i >= L; i--) for (int a = 0; a < K; a++) for (int b = 0; b < K; b++) {
        for (pii NXT : adj[i * K + a]) DP[i][a][b] = min(DP[i][a][b], DP[i + 1][NXT.f % K][b] + NXT.s);
    }
    for (int i = mid + 1; i <= R; i++) for (int a = 0; a < K; a++) for (int b = 0; b < K; b++) {
        for (pii NXT : adj[(i - 1) * K + b]) DP[i][a][NXT.f % K] = min(DP[i][a][NXT.f % K], DP[i - 1][a][b] + NXT.s);
    }
    vector<int> todo[2]; for (int T : V) { pii P = Q[T];

        if (P.f / K <= mid && mid <= P.s / K) for (int i = 0; i < K; i++) {
            ans[T] = min(ans[T], DP[P.f / K][P.f % K][i] + DP[P.s / K][i][P.s % K]);
        }
        else todo[P.f / K > mid].pb(T);
    }
    divide(L, mid - 1, todo[0]); divide(mid + 1, R, todo[1]);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    cin >> K >> N >> M >> O; memset(ans, 0x3f, sizeof ans);

    for (int i = 0; i < M; i++) { int A, B, T; cin >> A >> B >> T; adj[A].pb({B, T}); }

    vector<int> todo; for (int i = 0; i < O; i++) { int A, B; cin >> A >> B; Q.pb({A, B}); todo.pb(i); }

    divide(0, N / K, todo); for (int i = 0; i < O; i++) cout << ((ans[i] == INF) ? -1 : ans[i]) << "\n";
}

Compilation message (stderr)

toll.cpp: In function 'void divide(int, int, std::vector<int>)':
toll.cpp:18:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |     if (R < L) return ; int mid = (L + R) / 2;
      |     ^~
toll.cpp:18:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |     if (R < L) return ; int mid = (L + R) / 2;
      |                         ^~~

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