oj.uz

Submission #971227

# Submission time Handle Problem Language Result Execution time Memory
971227 2024-04-28T08:05:47 Z vyshniak_n Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 831 ms 73808 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

typedef long long ll;
typedef long double ld;

using namespace std;

#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define popb pop_back
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const ll N = 1e5 + 10;
const ll INF = 2e18 + 10;
const ll inf = 2e9 + 10;

vector <point> gr[N], ngr[3 * N];
ll dist[4][3 * N], tin[N], timer = 0;

void solve() {
    ll n, m;
    cin >> n >> m;

    ll s, t, u, v;
    cin >> s >> t >> u >> v;

    ll a[m], b[m], c[m];
    for (ll i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];

        gr[a[i]].pb(make_pair(b[i], c[i]));
        gr[b[i]].pb(make_pair(a[i], c[i]));
    }

    set <point> st;
    for (ll i = 1; i <= 3 * n; i++)
        dist[0][i] = dist[1][i] = dist[2][i] = dist[3][i] = INF;

    st.insert({0, s});
    dist[0][s] = 0;

    while (!st.empty()) {
        ll ver = st.begin()->ss;
        st.erase(st.begin());

        tin[ver] = ++timer;

        for (point to : gr[ver]) {
            if (dist[0][to.ff] > dist[0][ver] + to.ss) {
                st.erase(make_pair(dist[0][to.ff], to.ff));
                dist[0][to.ff] = dist[0][ver] + to.ss;
                st.insert(make_pair(dist[0][to.ff], to.ff));
            }
        }
    }

    st.insert({0, t});
    dist[1][t] = 0;

    while (!st.empty()) {
        ll ver = st.begin()->ss;
        st.erase(st.begin());

        for (point to : gr[ver]) {
            if (dist[1][to.ff] > dist[1][ver] + to.ss) {
                st.erase(make_pair(dist[1][to.ff], to.ff));
                dist[1][to.ff] = dist[1][ver] + to.ss;
                st.insert(make_pair(dist[1][to.ff], to.ff));
            }
        }
    }

    ll way = dist[0][t];

    for (ll i = 0; i < m; i++) {
        if (tin[a[i]] > tin[b[i]])
            swap(a[i], b[i]);

        ngr[a[i]].pb(make_pair(b[i], c[i]));
        ngr[b[i]].pb(make_pair(a[i], c[i]));

        ngr[a[i] + 2 * n].pb(make_pair(b[i] + 2 * n, c[i]));
        ngr[b[i] + 2 * n].pb(make_pair(a[i] + 2 * n, c[i]));

        if (dist[0][a[i]] + c[i] + dist[1][b[i]] == way)
            ngr[a[i] + n].pb(make_pair(b[i] + n, 0));
    }

    for (ll i = 1; i <= n; i++) {
        ngr[i].pb(make_pair(i + n, 0));
        ngr[i + n].pb(make_pair(i + 2 * n, 0));
    }

    st.insert({0, u});
    dist[2][u] = 0;

    while (!st.empty()) {
        ll ver = st.begin()->ss;
        st.erase(st.begin());

        for (point to : ngr[ver]) {
            if (dist[2][to.ff] > dist[2][ver] + to.ss) {
                st.erase(make_pair(dist[2][to.ff], to.ff));
                dist[2][to.ff] = dist[2][ver] + to.ss;
                st.insert(make_pair(dist[2][to.ff], to.ff));
            }
        }
    }

    st.insert({0, v});
    dist[3][v] = 0;

    while (!st.empty()) {
        ll ver = st.begin()->ss;
        st.erase(st.begin());

        for (point to : ngr[ver]) {
            if (dist[3][to.ff] > dist[3][ver] + to.ss) {
                st.erase(make_pair(dist[3][to.ff], to.ff));
                dist[3][to.ff] = dist[3][ver] + to.ss;
                st.insert(make_pair(dist[3][to.ff], to.ff));
            }
        }
    }

    cout << min(dist[2][v + 2 * n], dist[3][u + 2 * n]) << el;
    return;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tests = 1;
    //cin >> tests;

    while (tests--)
        solve();
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 69440 KB Output is correct
2 Correct 706 ms 67800 KB Output is correct
3 Correct 710 ms 70644 KB Output is correct
4 Correct 667 ms 69712 KB Output is correct
5 Correct 653 ms 68388 KB Output is correct
6 Correct 686 ms 69728 KB Output is correct
7 Correct 643 ms 68304 KB Output is correct
8 Correct 633 ms 68212 KB Output is correct
9 Correct 646 ms 68440 KB Output is correct
10 Correct 523 ms 70128 KB Output is correct
11 Correct 326 ms 50240 KB Output is correct
12 Correct 722 ms 67908 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 67720 KB Output is correct
2 Correct 681 ms 66916 KB Output is correct
3 Correct 644 ms 66900 KB Output is correct
4 Correct 693 ms 66664 KB Output is correct
5 Correct 715 ms 67176 KB Output is correct
6 Correct 648 ms 70484 KB Output is correct
7 Correct 679 ms 68552 KB Output is correct
8 Correct 682 ms 66900 KB Output is correct
9 Correct 709 ms 67064 KB Output is correct
10 Correct 697 ms 66908 KB Output is correct
11 Correct 309 ms 52220 KB Output is correct
12 Correct 647 ms 70676 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24924 KB Output is correct
2 Correct 5 ms 20060 KB Output is correct
3 Correct 4 ms 19804 KB Output is correct
4 Correct 19 ms 29532 KB Output is correct
5 Correct 14 ms 24644 KB Output is correct
6 Correct 5 ms 20060 KB Output is correct
7 Correct 6 ms 20316 KB Output is correct
8 Correct 6 ms 20316 KB Output is correct
9 Correct 5 ms 20112 KB Output is correct
10 Correct 12 ms 24668 KB Output is correct
11 Correct 4 ms 19804 KB Output is correct
12 Correct 4 ms 19804 KB Output is correct
13 Correct 5 ms 19800 KB Output is correct
14 Correct 5 ms 20060 KB Output is correct
15 Correct 5 ms 20096 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 69440 KB Output is correct
2 Correct 706 ms 67800 KB Output is correct
3 Correct 710 ms 70644 KB Output is correct
4 Correct 667 ms 69712 KB Output is correct
5 Correct 653 ms 68388 KB Output is correct
6 Correct 686 ms 69728 KB Output is correct
7 Correct 643 ms 68304 KB Output is correct
8 Correct 633 ms 68212 KB Output is correct
9 Correct 646 ms 68440 KB Output is correct
10 Correct 523 ms 70128 KB Output is correct
11 Correct 326 ms 50240 KB Output is correct
12 Correct 722 ms 67908 KB Output is correct
13 Correct 708 ms 67720 KB Output is correct
14 Correct 681 ms 66916 KB Output is correct
15 Correct 644 ms 66900 KB Output is correct
16 Correct 693 ms 66664 KB Output is correct
17 Correct 715 ms 67176 KB Output is correct
18 Correct 648 ms 70484 KB Output is correct
19 Correct 679 ms 68552 KB Output is correct
20 Correct 682 ms 66900 KB Output is correct
21 Correct 709 ms 67064 KB Output is correct
22 Correct 697 ms 66908 KB Output is correct
23 Correct 309 ms 52220 KB Output is correct
24 Correct 647 ms 70676 KB Output is correct
25 Correct 12 ms 24924 KB Output is correct
26 Correct 5 ms 20060 KB Output is correct
27 Correct 4 ms 19804 KB Output is correct
28 Correct 19 ms 29532 KB Output is correct
29 Correct 14 ms 24644 KB Output is correct
30 Correct 5 ms 20060 KB Output is correct
31 Correct 6 ms 20316 KB Output is correct
32 Correct 6 ms 20316 KB Output is correct
33 Correct 5 ms 20112 KB Output is correct
34 Correct 12 ms 24668 KB Output is correct
35 Correct 4 ms 19804 KB Output is correct
36 Correct 4 ms 19804 KB Output is correct
37 Correct 5 ms 19800 KB Output is correct
38 Correct 5 ms 20060 KB Output is correct
39 Correct 5 ms 20096 KB Output is correct
40 Correct 827 ms 73608 KB Output is correct
41 Correct 660 ms 68332 KB Output is correct
42 Correct 734 ms 68692 KB Output is correct
43 Correct 332 ms 50792 KB Output is correct
44 Correct 323 ms 50512 KB Output is correct
45 Correct 681 ms 71164 KB Output is correct
46 Correct 622 ms 71392 KB Output is correct
47 Correct 831 ms 69528 KB Output is correct
48 Correct 346 ms 49788 KB Output is correct
49 Correct 601 ms 73376 KB Output is correct
50 Correct 686 ms 70480 KB Output is correct
51 Correct 620 ms 73808 KB Output is correct