oj.uz

Submission #244698

# Submission time Handle Problem Language Result Execution time Memory
244698 2020-07-04T15:52:01 Z santaclaus03 Toll (BOI17_toll) C++14
7 / 100
 355 ms 50040 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 main() {
    int K, n, m, o; cin >> K >> n >> m >> o;
    vvii rev(n);
    for (int i = 0; i < m; ++i) {
        int a, b, t; cin >> a >> b >> t;
        rev[b].emplace_back(t, a);
    }
    int S = (int) round(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);
                }
            }
        }
    }
    for (int i = 0; i < o; ++i) {
        int a, b; cin >> a >> b;
        if (b < a) {
            cout << -1 << endl;
            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.at(g1+1).at(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.at(g).at(k1), d.at(g-1).at(k2) + dist.at(g-1).at(k2).at(k1 + S));
                    }
                }
            }
            
            for (int k = 0; k < K; ++k) {
                ans = min(ans, d.at(g2).at(k) + dist[g2][k][b % S]);
            }
        }
        cout << (ans == INF ? -1 : ans) << endl;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 49916 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 384 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 10 ms 512 KB Output is correct
8 Correct 279 ms 50040 KB Output is correct
9 Correct 338 ms 49912 KB Output is correct
10 Correct 206 ms 48136 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 50040 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 384 KB Output is correct
5 Incorrect 5 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 49916 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 384 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 10 ms 512 KB Output is correct
8 Correct 279 ms 50040 KB Output is correct
9 Correct 338 ms 49912 KB Output is correct
10 Correct 206 ms 48136 KB Output is correct
11 Correct 355 ms 50040 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Incorrect 5 ms 256 KB Output isn't correct
16 Halted 0 ms 0 KB -