oj.uz

답안 #391045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391045 2021-04-17T16:09:34 Z Victor Toll (BOI17_toll) C++17
18 / 100
 3000 ms 8712 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);
    }

    int preva = -1;
    set<ii> pq;
    rep(i, 0, o) {
        int a, b;
        cin >> a >> b;

        if (preva != a) {
            fill(dist, dist + n, INF);
            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);
                }
            }
        }
        preva=a;
        if (dist[b] == INF)
            cout << "-1\n";
        else
            cout << dist[b] << endl;
    }
    return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3086 ms 5580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 5600 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 1 ms 1484 KB Output is correct
7 Correct 4 ms 1616 KB Output is correct
8 Correct 21 ms 1612 KB Output is correct
9 Correct 37 ms 6496 KB Output is correct
10 Correct 105 ms 8712 KB Output is correct
11 Correct 93 ms 7356 KB Output is correct
12 Correct 45 ms 6780 KB Output is correct
13 Correct 84 ms 7924 KB Output is correct
14 Correct 60 ms 5984 KB Output is correct
15 Correct 50 ms 5580 KB Output is correct
16 Correct 50 ms 5480 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 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 12 ms 1484 KB Output is correct
7 Correct 25 ms 1484 KB Output is correct
8 Correct 40 ms 1612 KB Output is correct
9 Correct 37 ms 1484 KB Output is correct
10 Correct 793 ms 5580 KB Output is correct
11 Correct 1692 ms 5700 KB Output is correct
12 Correct 1803 ms 6428 KB Output is correct
13 Correct 2167 ms 6596 KB Output is correct
14 Correct 1917 ms 6084 KB Output is correct
15 Correct 1176 ms 4292 KB Output is correct
16 Correct 1163 ms 4292 KB Output is correct

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 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 12 ms 1484 KB Output is correct
7 Correct 25 ms 1484 KB Output is correct
8 Correct 40 ms 1612 KB Output is correct
9 Correct 37 ms 1484 KB Output is correct
10 Correct 793 ms 5580 KB Output is correct
11 Correct 1692 ms 5700 KB Output is correct
12 Correct 1803 ms 6428 KB Output is correct
13 Correct 2167 ms 6596 KB Output is correct
14 Correct 1917 ms 6084 KB Output is correct
15 Correct 1176 ms 4292 KB Output is correct
16 Correct 1163 ms 4292 KB Output is correct
17 Execution timed out 3065 ms 5572 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3086 ms 5580 KB Time limit exceeded
2 Halted 0 ms 0 KB -