oj.uz

Submission #516997

# Submission time Handle Problem Language Result Execution time Memory
516997 2022-01-22T10:45:53 Z nighty Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 412 ms 18620 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});
    }
    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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 13228 KB Output is correct
2 Correct 257 ms 12508 KB Output is correct
3 Correct 355 ms 15640 KB Output is correct
4 Incorrect 242 ms 13644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 14132 KB Output is correct
2 Correct 374 ms 13876 KB Output is correct
3 Correct 398 ms 13744 KB Output is correct
4 Correct 366 ms 14312 KB Output is correct
5 Correct 380 ms 17720 KB Output is correct
6 Correct 369 ms 18620 KB Output is correct
7 Correct 385 ms 18472 KB Output is correct
8 Correct 412 ms 17480 KB Output is correct
9 Correct 397 ms 17792 KB Output is correct
10 Correct 362 ms 17084 KB Output is correct
11 Correct 128 ms 11896 KB Output is correct
12 Correct 400 ms 18612 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 295 ms 13228 KB Output is correct
2 Correct 257 ms 12508 KB Output is correct
3 Correct 355 ms 15640 KB Output is correct
4 Incorrect 242 ms 13644 KB Output isn't correct
5 Halted 0 ms 0 KB -