oj.uz

Submission #1006837

# Submission time Handle Problem Language Result Execution time Memory
1006837 2024-06-24T09:13:06 Z overwatch9 Toll (BOI17_toll) C++17
8 / 100
 3000 ms 7260 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];
int processed[maxn];
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});
    }
    for (int o = 1; o <= O; o++) {
        int st, ed;
        cin >> st >> ed;
        fill(dis, dis + N + 1, 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] == o)
                continue;
            processed[s] = o;
            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});
                }
            }
        }
        if (dis[ed] == 1e18)
            dis[ed] = -1;
        cout << dis[ed] << '\n';
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3064 ms 4692 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 3042 ms 5288 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 1628 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 1628 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 3 ms 1628 KB Output is correct
8 Correct 7 ms 1816 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 15 ms 4320 KB Output is correct
11 Correct 159 ms 5212 KB Output is correct
12 Correct 249 ms 6740 KB Output is correct
13 Correct 267 ms 7260 KB Output is correct
14 Correct 226 ms 5972 KB Output is correct
15 Correct 176 ms 4444 KB Output is correct
16 Correct 158 ms 4444 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 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 1628 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 3 ms 1628 KB Output is correct
8 Correct 7 ms 1816 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 15 ms 4320 KB Output is correct
11 Correct 159 ms 5212 KB Output is correct
12 Correct 249 ms 6740 KB Output is correct
13 Correct 267 ms 7260 KB Output is correct
14 Correct 226 ms 5972 KB Output is correct
15 Correct 176 ms 4444 KB Output is correct
16 Correct 158 ms 4444 KB Output is correct
17 Execution timed out 3070 ms 5340 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 3064 ms 4692 KB Time limit exceeded
2 Halted 0 ms 0 KB -