oj.uz

Submission #955382

# Submission time Handle Problem Language Result Execution time Memory
955382 2024-03-30T10:11:58 Z blackslex Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 235 ms 27444 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

int n, m, s, t, cs, ct, x, y, z;

int main() {
    scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &cs, &ct);
    vector<vector<pii>> v(n + 5, vector<pii>());
    while (m--) scanf("%d %d %d", &x, &y, &z), v[x].emplace_back(y, z), v[y].emplace_back(x, z);
    vector<ll> d(n + 5, 1e18);
    vector<vector<int>> par(n + 5, vector<int>());
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.emplace(d[s] = 0, s);
    while (!pq.empty()) {
        auto [nd, nn] = pq.top(); pq.pop();
        for (auto &[tn, td]: v[nn]) {
            if (d[tn] > d[nn] + td) par[tn].clear(), par[tn].emplace_back(nn), pq.emplace(d[tn] = d[nn] + td, tn);
            else if (d[tn] == d[nn] + td) par[tn].emplace_back(nn);
        }
    }
    vector<int> u{t};
    for (int i = 0; i < u.size(); i++) {
        for (auto &e: par[u.back()]) u.emplace_back(e);
    }
    for (auto &e: u) v[n + 1].emplace_back(e, 0), v[e].emplace_back(n + 1, 0);
    vector<ll> d2(n + 5, 1e18);
    pq.emplace(d2[cs] = 0, cs);
    while (!pq.empty()) {
        auto [nd, nn] = pq.top(); pq.pop();
        for (auto &[tn, td]: v[nn]) if (d2[tn] > d2[nn] + td) pq.emplace(d2[tn] = d2[nn] + td, tn);
    }
    printf("%lld", d2[ct]);
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < u.size(); i++) {
      |                     ~~^~~~~~~~~~
commuter_pass.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &cs, &ct);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:12:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     while (m--) scanf("%d %d %d", &x, &y, &z), v[x].emplace_back(y, z), v[y].emplace_back(x, z);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 20416 KB Output is correct
2 Correct 207 ms 22244 KB Output is correct
3 Correct 194 ms 27328 KB Output is correct
4 Correct 146 ms 20420 KB Output is correct
5 Correct 176 ms 26080 KB Output is correct
6 Correct 166 ms 24520 KB Output is correct
7 Incorrect 193 ms 25892 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 22984 KB Output is correct
2 Correct 210 ms 23028 KB Output is correct
3 Correct 187 ms 23800 KB Output is correct
4 Correct 210 ms 23080 KB Output is correct
5 Correct 189 ms 23440 KB Output is correct
6 Correct 187 ms 25500 KB Output is correct
7 Correct 235 ms 27444 KB Output is correct
8 Correct 188 ms 23096 KB Output is correct
9 Correct 183 ms 23600 KB Output is correct
10 Correct 200 ms 22640 KB Output is correct
11 Correct 82 ms 20420 KB Output is correct
12 Correct 178 ms 26052 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1880 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 12 ms 3776 KB Output is correct
5 Correct 6 ms 2136 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 20416 KB Output is correct
2 Correct 207 ms 22244 KB Output is correct
3 Correct 194 ms 27328 KB Output is correct
4 Correct 146 ms 20420 KB Output is correct
5 Correct 176 ms 26080 KB Output is correct
6 Correct 166 ms 24520 KB Output is correct
7 Incorrect 193 ms 25892 KB Output isn't correct
8 Halted 0 ms 0 KB -