oj.uz

Submission #1006876

# Submission time Handle Problem Language Result Execution time Memory
1006876 2024-06-24T09:27:57 Z overwatch9 Toll (BOI17_toll) C++17
18 / 100
 3000 ms 4948 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) {
  	fill(dis, dis + maxn, 1e18);
    dis[st] = 0;
    priority_queue <pair <ll, int>> pq;
    pq.push({0, st});
    while (!pq.empty()) {
        int s = pq.top().second;
        pq.pop();
        if (processed[s])
            continue;
        processed[s] = true;
        modified.push(s);
        for (auto i : adj[s]) {
            if (dis[i.first] > dis[s] + i.second) {
                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 3054 ms 3908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3676 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 2 ms 2140 KB Output is correct
8 Correct 2 ms 2140 KB Output is correct
9 Correct 11 ms 3604 KB Output is correct
10 Correct 31 ms 4692 KB Output is correct
11 Correct 24 ms 3932 KB Output is correct
12 Correct 15 ms 3572 KB Output is correct
13 Correct 33 ms 4940 KB Output is correct
14 Correct 20 ms 3672 KB Output is correct
15 Correct 17 ms 3420 KB Output is correct
16 Correct 17 ms 3432 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 4 ms 2032 KB Output is correct
7 Correct 6 ms 1884 KB Output is correct
8 Correct 11 ms 2120 KB Output is correct
9 Correct 9 ms 1884 KB Output is correct
10 Correct 17 ms 3620 KB Output is correct
11 Correct 158 ms 3824 KB Output is correct
12 Correct 260 ms 4944 KB Output is correct
13 Correct 273 ms 4948 KB Output is correct
14 Correct 225 ms 4176 KB Output is correct
15 Correct 188 ms 3416 KB Output is correct
16 Correct 149 ms 3420 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct
6 Correct 4 ms 2032 KB Output is correct
7 Correct 6 ms 1884 KB Output is correct
8 Correct 11 ms 2120 KB Output is correct
9 Correct 9 ms 1884 KB Output is correct
10 Correct 17 ms 3620 KB Output is correct
11 Correct 158 ms 3824 KB Output is correct
12 Correct 260 ms 4944 KB Output is correct
13 Correct 273 ms 4948 KB Output is correct
14 Correct 225 ms 4176 KB Output is correct
15 Correct 188 ms 3416 KB Output is correct
16 Correct 149 ms 3420 KB Output is correct
17 Execution timed out 3059 ms 3848 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 3054 ms 3908 KB Time limit exceeded
2 Halted 0 ms 0 KB -