oj.uz

Submission #1006868

# Submission time Handle Problem Language Result Execution time Memory
1006868 2024-06-24T09:25:41 Z overwatch9 Toll (BOI17_toll) C++17
10 / 100
 3000 ms 7080 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 50001;
vector <pair <int, int>> adj[maxn];
ll dis[maxn];
bool processed[maxn];
queue <int> modified;
ll dijkstra(int st, int ed) {
    dis[st] = 0;
    priority_queue <pair <ll, int>> pq;
    modified.push(st);
    pq.push({0, st});
    while (!pq.empty()) {
        int s = pq.top().second;
        pq.pop();
        if (processed[s])
            continue;
        processed[s] = true;
        for (auto i : adj[s]) {
            if (dis[i.first] > dis[s] + i.second) {
                if (dis[i.first] == 1e18)
                    modified.push(i.first);
                dis[i.first] = dis[s] + i.second;
                pq.push({-dis[i.first], i.first});
            }
        }
    }
    int ans = 0;
    if (ed != -1) {
        if (dis[ed] == 1e18)
            dis[ed] = -1;
        ans = dis[ed];
        while (!modified.empty()) {
            dis[modified.front()] = 1e18;
            processed[modified.front()] = false;
            modified.pop();
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int K, N, M, O;
    cin >> K >> N >> M >> O;
    for (int i = 0; i < M; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        adj[a].push_back({b, t});
    }
    fill(dis, dis + N + 1, 1e18);
    vector <pair <int, int>> queries(O);
    bool all0 = true;
    for (int i = 0; i < O; i++) {
        cin >> queries[i].first >> queries[i].second;
        if (queries[i].first != 0)
            all0 = false;
    }
    if (all0)
        dijkstra(0, -1);
    for (int i = 0; i < O; i++) {
        if (all0) {
            if (dis[queries[i].second] == 1e18)
                cout << -1 << '\n';
            else
                cout << dis[queries[i].second] << '\n';
        } else {
            cout << dijkstra(queries[i].first, queries[i].second) << '\n';
        }
    }
}

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3604 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1632 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 12 ms 4444 KB Output is correct
10 Correct 33 ms 6996 KB Output is correct
11 Correct 24 ms 5464 KB Output is correct
12 Correct 18 ms 4740 KB Output is correct
13 Correct 34 ms 7080 KB Output is correct
14 Correct 21 ms 5212 KB Output is correct
15 Correct 24 ms 4436 KB Output is correct
16 Correct 18 ms 4444 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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