oj.uz

Submission #391044

# Submission time Handle Problem Language Result Execution time Memory
391044 2021-04-17T16:06:47 Z Victor Toll (BOI17_toll) C++17
8 / 100
 3000 ms 9060 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 = b - 1; i >= (a); --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 umap unordered_map
#define uset unordered_set

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

const int INF = 1000000007;

vii graph[50001];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int k, n, m, o, dist[50001];
    cin >> k >> n >> m >> o;
    rep(i, 0, m) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
    }

    set<ii> pq;
    rep(i, 0, o) {
        fill(dist, dist + n, INF);
        int a, b;
        cin >> a >> b;
        dist[a] = 0;
        rep(i, 0, n) pq.insert({dist[i], i});

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

            trav(edge, graph[u]) {
                int v, w;
                tie(v, w) = edge;
                if (d+w>=dist[v])continue;

                pq.erase({dist[v],v});
                dist[v]=d+w;
                pq.emplace(d+w,v);
            }
        }
        if(dist[b]==INF)cout<<"-1\n";
        else cout<<dist[b]<<endl;
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 6448 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 3075 ms 7184 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 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 13 ms 1488 KB Output is correct
7 Correct 25 ms 1484 KB Output is correct
8 Correct 39 ms 1640 KB Output is correct
9 Correct 35 ms 1612 KB Output is correct
10 Correct 810 ms 6380 KB Output is correct
11 Correct 1589 ms 7104 KB Output is correct
12 Correct 1819 ms 8544 KB Output is correct
13 Correct 1968 ms 9060 KB Output is correct
14 Correct 1855 ms 7860 KB Output is correct
15 Correct 1103 ms 5444 KB Output is correct
16 Correct 1103 ms 5572 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 13 ms 1488 KB Output is correct
7 Correct 25 ms 1484 KB Output is correct
8 Correct 39 ms 1640 KB Output is correct
9 Correct 35 ms 1612 KB Output is correct
10 Correct 810 ms 6380 KB Output is correct
11 Correct 1589 ms 7104 KB Output is correct
12 Correct 1819 ms 8544 KB Output is correct
13 Correct 1968 ms 9060 KB Output is correct
14 Correct 1855 ms 7860 KB Output is correct
15 Correct 1103 ms 5444 KB Output is correct
16 Correct 1103 ms 5572 KB Output is correct
17 Execution timed out 3067 ms 7060 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 6448 KB Time limit exceeded
2 Halted 0 ms 0 KB -