oj.uz

Submission #517003

# Submission time Handle Problem Language Result Execution time Memory
517003 2022-01-22T11:00:26 Z nighty Commuter Pass (JOI18_commuter_pass) C++14
16 / 100
 2000 ms 15716 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;
    }

//    SUBTASK 2
//    dijkstra(s, g);
//    while (t >= 0) {
//        choosenE.insert({last[t], t});
//        t = last[t];
//    }
//    auto d = dijkstra2(u, g);
//    cout << d[v] << '\n';

    long long minDistST = dijkstra(s, g)[t], res = numeric_limits<long long>::max();;
    auto dT = dijkstra(t, g), dV = dijkstra(v, g), dS = dijkstra(s, g), dU = dijkstra(u, g);
    for (int i = 0; i < n; ++i) {
        auto di = dijkstra(i, g);
        for (int j = 0; j < n; ++j) {
            if (dS[i] + di[j] + dT[j] == minDistST) {
                res = min(res, min(dU[i] + dV[j], dV[i] + dU[j]));
            }
        }
    }
    cout << res << '\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 486 ms 14740 KB Output is correct
2 Correct 409 ms 13696 KB Output is correct
3 Correct 362 ms 13440 KB Output is correct
4 Correct 411 ms 14752 KB Output is correct
5 Correct 321 ms 13620 KB Output is correct
6 Correct 556 ms 14792 KB Output is correct
7 Correct 391 ms 13564 KB Output is correct
8 Correct 385 ms 13728 KB Output is correct
9 Correct 381 ms 13672 KB Output is correct
10 Correct 290 ms 13972 KB Output is correct
11 Correct 96 ms 8520 KB Output is correct
12 Correct 400 ms 13492 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 15716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1100 KB Output is correct
2 Incorrect 32 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 14740 KB Output is correct
2 Correct 409 ms 13696 KB Output is correct
3 Correct 362 ms 13440 KB Output is correct
4 Correct 411 ms 14752 KB Output is correct
5 Correct 321 ms 13620 KB Output is correct
6 Correct 556 ms 14792 KB Output is correct
7 Correct 391 ms 13564 KB Output is correct
8 Correct 385 ms 13728 KB Output is correct
9 Correct 381 ms 13672 KB Output is correct
10 Correct 290 ms 13972 KB Output is correct
11 Correct 96 ms 8520 KB Output is correct
12 Correct 400 ms 13492 KB Output is correct
13 Execution timed out 2079 ms 15716 KB Time limit exceeded
14 Halted 0 ms 0 KB -