oj.uz

Submission #517000

# Submission time Handle Problem Language Result Execution time Memory
517000 2022-01-22T10:54:21 Z nighty Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 456 ms 15352 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> last;

set<pair<int, int>> choosenE;

vector<long long> dijkstra(int start, vector<vector<pair<int, int>>>& g) {
    int n = g.size();
    vector<long long> d(n, numeric_limits<long long>::max());
    last.assign(n, -1);
    d[start] = 0;
    set<pair<long long, int>> s; // {d[i], i}
    s.insert({0, start});
    while (!s.empty()) {
        int i = s.begin()->second;
        s.erase(s.begin());
        for (auto [j, w] : g[i]) {
            if (d[i] + w < d[j]) {
                s.erase({d[j], j});
                d[j] = d[i] + w;
                last[j] = i;
                s.insert({d[j], j});
            }
        }
    }
    return d;
}

vector<long long> dijkstra2(int start, vector<vector<pair<int, int>>>& g) {
    int n = g.size();
    vector<long long> d(n, numeric_limits<long long>::max());
    last.assign(n, -1);
    d[start] = 0;
    set<pair<long long, int>> s; // {d[i], i}
    s.insert({0, start});
    while (!s.empty()) {
        int i = s.begin()->second;
        s.erase(s.begin());
        for (auto [j, w] : g[i]) {
            if (choosenE.find({i, j}) != choosenE.end() || choosenE.find({j, i}) != choosenE.end()) {
                w = 0;
            }
            if (d[i] + w < d[j]) {
                s.erase({d[j], j});
                d[j] = d[i] + w;
                last[j] = i;
                s.insert({d[j], j});
            }
        }
    }
    return d;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int s, t;
    cin >> s >> t;
    --s, --t;
    int u, v;
    cin >> u >> v;
    --u, --v;
    vector<vector<pair<int, int>>> g(n);
    for (int _m = 0; _m < m; ++_m) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    if (s == u) {
        long long minDistST = dijkstra(s, g)[t];
        auto dT = dijkstra(t, g), dV = dijkstra(v, g), dS = dijkstra(s, g);
        long long res = numeric_limits<long long>::max();
        for (int i = 0; i < n; ++i) {
            if (dS[i] + dT[i] == minDistST) {
                res = min(res, dV[i]);
            }
        }
        cout << res << '\n';
        return 0;
    }
    dijkstra(s, g);
    while (t >= 0) {
        choosenE.insert({last[t], t});
        t = last[t];
    }
    auto d = dijkstra2(u, g);
    cout << d[v] << '\n';
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int, std::vector<std::vector<std::pair<int, int> > >&)':
commuter_pass.cpp:19:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |         for (auto [j, w] : g[i]) {
      |                   ^
commuter_pass.cpp: In function 'std::vector<long long int> dijkstra2(int, std::vector<std::vector<std::pair<int, int> > >&)':
commuter_pass.cpp:41:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for (auto [j, w] : g[i]) {
      |                   ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 14644 KB Output is correct
2 Correct 370 ms 13640 KB Output is correct
3 Correct 350 ms 13452 KB Output is correct
4 Correct 428 ms 14840 KB Output is correct
5 Correct 369 ms 14136 KB Output is correct
6 Correct 456 ms 15352 KB Output is correct
7 Correct 384 ms 14228 KB Output is correct
8 Correct 354 ms 14240 KB Output is correct
9 Correct 394 ms 14208 KB Output is correct
10 Correct 276 ms 14468 KB Output is correct
11 Correct 104 ms 9036 KB Output is correct
12 Correct 403 ms 14212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 13892 KB Output is correct
2 Correct 393 ms 13828 KB Output is correct
3 Correct 427 ms 13160 KB Output is correct
4 Correct 388 ms 13748 KB Output is correct
5 Correct 408 ms 14276 KB Output is correct
6 Correct 380 ms 14644 KB Output is correct
7 Correct 430 ms 15112 KB Output is correct
8 Correct 387 ms 13840 KB Output is correct
9 Correct 405 ms 14196 KB Output is correct
10 Correct 375 ms 13496 KB Output is correct
11 Correct 143 ms 9780 KB Output is correct
12 Correct 413 ms 14900 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 14644 KB Output is correct
2 Correct 370 ms 13640 KB Output is correct
3 Correct 350 ms 13452 KB Output is correct
4 Correct 428 ms 14840 KB Output is correct
5 Correct 369 ms 14136 KB Output is correct
6 Correct 456 ms 15352 KB Output is correct
7 Correct 384 ms 14228 KB Output is correct
8 Correct 354 ms 14240 KB Output is correct
9 Correct 394 ms 14208 KB Output is correct
10 Correct 276 ms 14468 KB Output is correct
11 Correct 104 ms 9036 KB Output is correct
12 Correct 403 ms 14212 KB Output is correct
13 Correct 433 ms 13892 KB Output is correct
14 Correct 393 ms 13828 KB Output is correct
15 Correct 427 ms 13160 KB Output is correct
16 Correct 388 ms 13748 KB Output is correct
17 Correct 408 ms 14276 KB Output is correct
18 Correct 380 ms 14644 KB Output is correct
19 Correct 430 ms 15112 KB Output is correct
20 Correct 387 ms 13840 KB Output is correct
21 Correct 405 ms 14196 KB Output is correct
22 Correct 375 ms 13496 KB Output is correct
23 Correct 143 ms 9780 KB Output is correct
24 Correct 413 ms 14900 KB Output is correct
25 Incorrect 7 ms 972 KB Output isn't correct
26 Halted 0 ms 0 KB -