oj.uz

Submission #599536

# Submission time Handle Problem Language Result Execution time Memory
599536 2022-07-19T15:17:49 Z pedroslrey Toll (BOI17_toll) C++17
8 / 100
 3000 ms 6880 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e4 + 10;

vector<pair<int, int>> graph[MAXN];
int dist[MAXN];
bool marc[MAXN];

void dijkstra(int a, int n) {
    for (int i = 0; i < n; ++i) {
        dist[i] = 1e9;
        marc[i] = false;
    }

    set<pair<int, int>> s;
    s.emplace(0, a);
    dist[a] = 0;

    while (!s.empty()) {
        int u = s.begin()->second; s.erase(s.begin());

        if (marc[u]) continue;
        marc[u] = true;

        for (auto [v, c]: graph[u]) {
            int d = dist[u] + c;
            if (dist[v] > d) {
                dist[v] = d;
                s.emplace(d, v);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q, m, k;
    cin >> k >> n >> m >> q;

    for (int i = 0; i < m; ++i) {
        int u, v, t;
        cin >> u >> v >> t;

        graph[u].emplace_back(v, t);
    }

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

        dijkstra(a, n);

        if (marc[b]) cout << dist[b] << "\n";
        else cout << "-1\n";
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 3296 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 3082 ms 3284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 8 ms 1492 KB Output is correct
8 Correct 18 ms 1644 KB Output is correct
9 Correct 13 ms 1560 KB Output is correct
10 Correct 27 ms 4044 KB Output is correct
11 Correct 439 ms 4812 KB Output is correct
12 Correct 575 ms 6376 KB Output is correct
13 Correct 806 ms 6880 KB Output is correct
14 Correct 625 ms 5612 KB Output is correct
15 Correct 428 ms 4124 KB Output is correct
16 Correct 408 ms 4156 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 3 ms 1492 KB Output is correct
7 Correct 8 ms 1492 KB Output is correct
8 Correct 18 ms 1644 KB Output is correct
9 Correct 13 ms 1560 KB Output is correct
10 Correct 27 ms 4044 KB Output is correct
11 Correct 439 ms 4812 KB Output is correct
12 Correct 575 ms 6376 KB Output is correct
13 Correct 806 ms 6880 KB Output is correct
14 Correct 625 ms 5612 KB Output is correct
15 Correct 428 ms 4124 KB Output is correct
16 Correct 408 ms 4156 KB Output is correct
17 Execution timed out 3086 ms 4848 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 3070 ms 3296 KB Time limit exceeded
2 Halted 0 ms 0 KB -