oj.uz

Submission #865400

# Submission time Handle Problem Language Result Execution time Memory
865400 2023-10-24T07:55:55 Z Asamai Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 247 ms 20604 KB 
#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
#define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;

int n, m, s, t, x, y;
int go[MAX_N], back[MAX_N];
vector<pii> adj[MAX_N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t >> x >> y;
    for (int i = 1; i <= m; i++) {
        int U, V, C;
        cin >> U >> V >> C;
        adj[U].pb({V, C});
        adj[V].pb({U, C});
    }

    for (int i = 1; i <= n; i++) {
        go[i] = inf;
    }
    go[s] = 0;
    pq.push({go[s], s});
    while (!pq.empty()) {
        int u = pq.top().se;
        int currW = pq.top().fi;

        pq.pop();

        if (currW > go[u]) {
            continue;
        }

        for (auto it : adj[u]) {
            int v = it.fi;
            int w = it.se;
            if (currW + w < go[v]) {
                go[v] = currW + w;
                pq.push({go[v], v});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        back[i] = inf;
    }
    back[t] = 0;
    pq.push({back[t], t});
    while (!pq.empty()) {
        int u = pq.top().se;
        int currW = pq.top().fi;

        pq.pop();

        if (currW > back[u]) {
            continue;
        }

        for (auto it : adj[u]) {
            int v = it.fi;
            int w = it.se;
            if (currW + w < back[v]) {
                back[v] = currW + w;
                pq.push({back[v], v});
            }
        }
    }

    for (int u = 1; u <= n; u++) {
        for (auto &it : adj[u]) {
            int v = it.fi;
            int w = it.se;
            if (go[u] + w + back[v] == go[t] || back[u] + w + go[v] == go[t]) {
                it.se = 0;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        go[i] = inf;
    }
    go[x] = 0;
    pq.push({go[x], x});
    while (!pq.empty()) {
        int u = pq.top().se;
        int currW = pq.top().fi;

        pq.pop();

        if (currW > go[u]) {
            continue;
        }

        for (auto it : adj[u]) {
            int v = it.fi;
            int w = it.se;
            if (currW + w < go[v]) {
                go[v] = currW + w;
                pq.push({go[v], v});
            }
        }
    }

    cout << go[y];

    return 0;
}

/*


Tuesday, 24 October 2023
14:22:00
*/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 19780 KB Output is correct
2 Correct 151 ms 19136 KB Output is correct
3 Correct 153 ms 20416 KB Output is correct
4 Correct 143 ms 19640 KB Output is correct
5 Correct 148 ms 18988 KB Output is correct
6 Correct 177 ms 19916 KB Output is correct
7 Correct 152 ms 19168 KB Output is correct
8 Correct 155 ms 19144 KB Output is correct
9 Correct 146 ms 19804 KB Output is correct
10 Correct 127 ms 19912 KB Output is correct
11 Correct 51 ms 11620 KB Output is correct
12 Correct 159 ms 19744 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 20604 KB Output is correct
2 Correct 187 ms 19368 KB Output is correct
3 Correct 191 ms 20252 KB Output is correct
4 Correct 217 ms 19144 KB Output is correct
5 Correct 196 ms 19404 KB Output is correct
6 Correct 188 ms 19504 KB Output is correct
7 Correct 247 ms 20216 KB Output is correct
8 Correct 201 ms 19284 KB Output is correct
9 Correct 208 ms 20172 KB Output is correct
10 Correct 219 ms 19404 KB Output is correct
11 Correct 76 ms 11676 KB Output is correct
12 Correct 200 ms 19500 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4444 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 19780 KB Output is correct
2 Correct 151 ms 19136 KB Output is correct
3 Correct 153 ms 20416 KB Output is correct
4 Correct 143 ms 19640 KB Output is correct
5 Correct 148 ms 18988 KB Output is correct
6 Correct 177 ms 19916 KB Output is correct
7 Correct 152 ms 19168 KB Output is correct
8 Correct 155 ms 19144 KB Output is correct
9 Correct 146 ms 19804 KB Output is correct
10 Correct 127 ms 19912 KB Output is correct
11 Correct 51 ms 11620 KB Output is correct
12 Correct 159 ms 19744 KB Output is correct
13 Correct 177 ms 20604 KB Output is correct
14 Correct 187 ms 19368 KB Output is correct
15 Correct 191 ms 20252 KB Output is correct
16 Correct 217 ms 19144 KB Output is correct
17 Correct 196 ms 19404 KB Output is correct
18 Correct 188 ms 19504 KB Output is correct
19 Correct 247 ms 20216 KB Output is correct
20 Correct 201 ms 19284 KB Output is correct
21 Correct 208 ms 20172 KB Output is correct
22 Correct 219 ms 19404 KB Output is correct
23 Correct 76 ms 11676 KB Output is correct
24 Correct 200 ms 19500 KB Output is correct
25 Correct 8 ms 4444 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Incorrect 1 ms 2652 KB Output isn't correct
28 Halted 0 ms 0 KB -