oj.uz

Submission #349812

# Submission time Handle Problem Language Result Execution time Memory
349812 2021-01-18T12:45:09 Z Victor Toll (BOI17_toll) C++17
8 / 100
 3000 ms 14828 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = a - 1; i >= (b); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define endl '\n'

#define umap unordered_map
#define uset unordered_set
#define INF 1000000000

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    set<pair<ll, int>> s, pq;
    vector<ll> dist;
    vector<pair<int, ll>> graph[50001];
    int k, n, m, o;
    cin >> k >> n >> m >> o;

    rep(i, 0, m) {
        ll a, b, t;
        cin >> a >> b >> t;
        graph[a].emplace_back(b, t);
    }

    rep(i, 0, n) s.emplace(1e15, i);
    while (o--) {
        dist.assign(n, 1e15);
        pq = s;
        ll a, b;
        cin >> a >> b;
        pq.erase({1e15, a});
        pq.emplace(0, a);

        while (!pq.empty()) {
            ll cost, u;
            tie(cost, u) = *pq.begin();
            pq.erase(pq.begin());

            trav(edge, graph[u]) {
                ll w = edge.second;
                int v = edge.first;
                if (cost + w >= dist[v]) continue;
                pq.erase({dist[v], v});
                pq.insert({cost + w, v});
                dist[v] = cost + w;
            }
        }

        if (dist[b] == 1e15) cout<<-1<<endl;
        else cout<<dist[b]<<endl;
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 10712 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 3084 ms 12268 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 1516 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 1 ms 1516 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 10 ms 1644 KB Output is correct
7 Correct 26 ms 1772 KB Output is correct
8 Correct 35 ms 1900 KB Output is correct
9 Correct 34 ms 1900 KB Output is correct
10 Correct 645 ms 10604 KB Output is correct
11 Correct 1685 ms 12268 KB Output is correct
12 Correct 1972 ms 14188 KB Output is correct
13 Correct 2570 ms 14828 KB Output is correct
14 Correct 2129 ms 13036 KB Output is correct
15 Correct 1127 ms 8684 KB Output is correct
16 Correct 1090 ms 8684 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1516 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 1 ms 1516 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
6 Correct 10 ms 1644 KB Output is correct
7 Correct 26 ms 1772 KB Output is correct
8 Correct 35 ms 1900 KB Output is correct
9 Correct 34 ms 1900 KB Output is correct
10 Correct 645 ms 10604 KB Output is correct
11 Correct 1685 ms 12268 KB Output is correct
12 Correct 1972 ms 14188 KB Output is correct
13 Correct 2570 ms 14828 KB Output is correct
14 Correct 2129 ms 13036 KB Output is correct
15 Correct 1127 ms 8684 KB Output is correct
16 Correct 1090 ms 8684 KB Output is correct
17 Execution timed out 3082 ms 12268 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 3080 ms 10712 KB Time limit exceeded
2 Halted 0 ms 0 KB -