Submission #245080

#	Time	Username	Problem	Language	Result	Execution time	Memory
245080		santaclaus03	Toll (BOI17_toll)	C++14	100 / 100	662 ms	55508 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vvii = vector<vector<ii>>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

#define INF 1000000000

int K, N, M, O; 
vvii rev;
vector<ii> queries;

vi sqrt_dcmp() {
    int S = (int) sqrt(N);
    int G = (int) ceil((double) N / S);
    vvvi dist(G, vvi(S + K * 2, vi(S + K * 2, INF)));
    for (int g = 0; g < G; ++g) {
        for (int u = 0; u < S + K * 2; ++u) {
            dist[g][u][u] = 0;
            for (int v = u + 1; v < S + K * 2; ++v) {
                if (u + g * S >= N || v + g * S >= N) continue;
                for (ii e : rev[v + g * S]) {
                    int w = e.second - g * S;
                    if (w < u) continue;
                    dist[g][u][v] = min(dist[g][u][v], dist[g][u][w] + e.first);
                }
            }
        }
    }
    vi answers;
    for (ii q : queries) {
        int a = q.first, b = q.second;
        if (b < a) {
            answers.push_back(-1);
            continue;
        }
        int ans = INF;
        int g1 = a / S, g2 = b / S;
        if (g1 == g2) {
            ans = dist[g1][a % S][b % S];
        } else {
            vvi d(G, vi(K * 2, INF));
            for (int k = 0; k < K * 2; ++k) {
                d[g1+1][k] = dist[g1][a % S][k + S];
            }
            for (int g = g1 + 2; g <= g2; ++g) {
                for (int k1 = 0; k1 < K * 2; ++k1) {
                    for (int k2 = 0; k2 < K * 2; ++k2) {
                        d[g][k1] = min(d[g][k1], d[g-1][k2] + dist[g-1][k2][k1 + S]);
                    }
                }
            }
            for (int k = 0; k < K * 2; ++k) {
                ans = min(ans, d[g2][k] + dist[g2][k][b % S]);
            }
        }
        answers.push_back(ans == INF ? -1 : ans);
    }
    return answers;
}

vi bruteforce() {
    vi d0(N, INF);
    d0[0] = 0;
    for (int u = 1; u < N; ++u)
    {
        for (ii e : rev[u])
        {
            d0[u] = min(d0[u], d0[e.second] + e.first);
        }
    }
    vi answers;
    for (ii q : queries)
    {
        int a = q.first, b = q.second;
        int ans;
        if (a == 0) {
            ans = d0[b];
        }
        else
        {
            vi d(N, INF);
            d[a] = 0;
            for (int u = a + 1; u < N; ++u)
            {
                for (ii e : rev[u])
                {
                    d[u] = min(d[u], d[e.second] + e.first);
                }
            }
            ans = d[b];
        }
        answers.push_back(ans == INF ? -1 : ans);
    }
    return answers;
}

int main() {
    //freopen("out.txt", "w", stdout);
    //freopen("in.txt", "r", stdin);
    cin >> K >> N >> M >> O;
    rev.resize(N);
    queries.resize(O);
    for (int i = 0; i < M; ++i) {
        int a, b, t; cin >> a >> b >> t;
        rev[b].emplace_back(t, a);
    }
    for (int i = 0; i < O; ++i) cin >> queries[i].first >> queries[i].second;
    //vi expected = bruteforce();
    vi actual = sqrt_dcmp();
    //cout << "sqrt dcmp ok" << endl;
    for (int i = 0; i < O; ++i) {
        //if (expected[i] != actual[i]) {
        //    cout << queries[i].first << " " << queries[i].second << endl;
        //    cout << "Expected: " << expected[i] << ", Actual: " << actual[i] << endl;
        //}
        cout << actual[i] << endl;
    }
    return 0;
}

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