oj.uz

Submission #244993

# Submission time Handle Problem Language Result Execution time Memory
244993 2020-07-05T10:43:30 Z santaclaus03 Toll (BOI17_toll) C++14
46 / 100
 1159 ms 49768 KB 
#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, vi(S + K, INF)));
    for (int g = 0; g < G; ++g) {
        for (int u = 0; u < S + K; ++u) {
            dist[g][u][u] = 0;
            for (int v = u + 1; v < S + K; ++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, INF));
            for (int k = 0; k < K; ++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; ++k1) {
                    for (int k2 = 0; k2 < K; ++k2) {
                        d[g][k1] = min(d[g][k1], d[g-1][k2] + dist[g-1][k2][k1 + S]);
                    }
                }
            }
            for (int k = 0; k < K; ++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() {
    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 = (O <= 3000 ||N * K <= 20000) ? bruteforce() : sqrt_dcmp();
    //vi actual = sqrt_dcmp();
    for (int i = 0; i < O; ++i) {
        //cout << "Expected: " << expected[i] << ", Actual: " << actual[i] << endl;
        cout << expected[i] << endl;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 49528 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 11 ms 384 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 278 ms 49656 KB Output is correct
9 Correct 275 ms 49500 KB Output is correct
10 Correct 186 ms 47992 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 359 ms 49768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 128 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 10 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct
10 Correct 83 ms 3508 KB Output is correct
11 Correct 149 ms 3508 KB Output is correct
12 Correct 207 ms 4344 KB Output is correct
13 Correct 237 ms 4756 KB Output is correct
14 Correct 184 ms 4088 KB Output is correct
15 Correct 120 ms 2552 KB Output is correct
16 Correct 117 ms 2552 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 128 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 10 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct
10 Correct 83 ms 3508 KB Output is correct
11 Correct 149 ms 3508 KB Output is correct
12 Correct 207 ms 4344 KB Output is correct
13 Correct 237 ms 4756 KB Output is correct
14 Correct 184 ms 4088 KB Output is correct
15 Correct 120 ms 2552 KB Output is correct
16 Correct 117 ms 2552 KB Output is correct
17 Correct 796 ms 3580 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 4 ms 256 KB Output is correct
20 Correct 4 ms 256 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 26 ms 512 KB Output is correct
24 Correct 24 ms 512 KB Output is correct
25 Correct 39 ms 512 KB Output is correct
26 Correct 31 ms 504 KB Output is correct
27 Correct 574 ms 3636 KB Output is correct
28 Correct 1141 ms 4660 KB Output is correct
29 Correct 1159 ms 4728 KB Output is correct
30 Correct 1104 ms 4252 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 49528 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 11 ms 384 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 278 ms 49656 KB Output is correct
9 Correct 275 ms 49500 KB Output is correct
10 Correct 186 ms 47992 KB Output is correct
11 Incorrect 359 ms 49768 KB Output isn't correct
12 Halted 0 ms 0 KB -