oj.uz

Submission #245182

# Submission time Handle Problem Language Result Execution time Memory
245182 2020-07-05T16:31:22 Z Tc14 Toll (BOI17_toll) C++17
8 / 100
 3000 ms 6532 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;

const int INF = 1e9;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int k, n, m, o, a, b, t, u, v, d, dNew;
    ve<ve<pair<int, int>>> G;
    ve<int> D;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;

    cin >> k >> n >> m >> o;
    G = ve<ve<pair<int, int>>>(n);

    for (int i = 0; i < m; i++) {
        cin >> a >> b >> t;
        G[a].push_back({b, t});
    }

    for (int i = 0; i < o; i++) {
        cin >> a >> b;

        D = vector<int>(n, INF);
        D[a] = 0;
        PQ.push({0, a});

        while (!PQ.empty()) {
            tie(d, u) = PQ.top();
            PQ.pop();
            for (pair<int, int> e : G[u]) {
                tie(v, t) = e;
                dNew = d + t;
                if (dNew < D[v]) {
                    D[v] = dNew;
                    PQ.push({dNew, v});
                }
            }
        }

        if (D[b] == INF) cout << -1 << endl;
        else cout << D[b] << endl;
    }

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 3916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 3656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 9 ms 384 KB Output is correct
8 Correct 17 ms 512 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 33 ms 4276 KB Output is correct
11 Correct 296 ms 5056 KB Output is correct
12 Correct 401 ms 6384 KB Output is correct
13 Correct 467 ms 6532 KB Output is correct
14 Correct 383 ms 6004 KB Output is correct
15 Correct 254 ms 3840 KB Output is correct
16 Correct 251 ms 3832 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 9 ms 384 KB Output is correct
8 Correct 17 ms 512 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 33 ms 4276 KB Output is correct
11 Correct 296 ms 5056 KB Output is correct
12 Correct 401 ms 6384 KB Output is correct
13 Correct 467 ms 6532 KB Output is correct
14 Correct 383 ms 6004 KB Output is correct
15 Correct 254 ms 3840 KB Output is correct
16 Correct 251 ms 3832 KB Output is correct
17 Execution timed out 3058 ms 5216 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 3916 KB Time limit exceeded
2 Halted 0 ms 0 KB -