oj.uz

Submission #357703

# Submission time Handle Problem Language Result Execution time Memory
357703 2021-01-24T13:05:38 Z cute_hater Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 423 ms 31572 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>


/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 1e5 + 7, INF = 1e18;

vector <pi> g[N];
vector <int> ng[N];
int dist[4][N], dp[2][N];
ti ed[2 * N];
bool good[N], used[N];

void dijkstra(int fst, int f) {
    priority_queue <pi, vector <pi>, greater <pi> > q;
    q.push({ 0, fst });
    loop(i, N)
        dist[f][i] = INF;
    dist[f][fst] = 0;
    while (!q.empty()) {
        int v = q.top().S, dv = q.top().F;
        q.pop();
        if (dv > dist[f][v])
            continue;
        for (pi u : g[v])
            if (dist[f][u.F] > dist[f][v] + u.S) {
                dist[f][u.F] = dist[f][v] + u.S;
                q.push({ dist[f][u.F], u.F });
            }
    }
}

void dfs(int v, int a, int b) {
    used[v] = 1;
    dp[0][v] = dist[2][v];
    dp[1][v] = dist[3][v];
    for (int u : ng[v]) {
        if (!used[u])
            dfs(u, a, b);
        dp[0][v] = min(dp[0][v], dp[0][u]);
        dp[1][v] = min(dp[1][v], dp[1][u]);
    }
}

void solve() {
    int n, m, s, t, a, b;
    cin >> n >> m >> s >> t >> a >> b;
    loop(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].pb({ v, c });
        g[v].pb({ u, c });
        ed[i] = mkt(u, v, c);
    }
    dijkstra(s, 0);
    dijkstra(t, 1);
    dijkstra(a, 2);
    dijkstra(b, 3);
    int len = dist[0][t];
    loop(i, m) {
        int u, v, c;
        tie(u, v, c) = ed[i];
        if (dist[0][u] + c + dist[1][v] == len || dist[0][v] + c + dist[1][u] == len) {
            good[u] = good[v] = 1;
            if (dist[0][u] < dist[0][v])
                ng[u].pb(v);
            else
                ng[v].pb(u);
        }
    }
    int ans = dist[3][a];
    loop1(i, n) {
        if (good[i]) {
            if (!used[i])
                dfs(i, a, b);
            ans = min({ ans, dp[0][i] + dist[3][i], dp[1][i] + dist[2][i] });
        }
    }
    cout << ans;
}

signed main() {
    //freopen("b2.txt", "r", stdin);
    //freopen("ans9.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 26944 KB Output is correct
2 Correct 368 ms 25864 KB Output is correct
3 Correct 392 ms 29664 KB Output is correct
4 Correct 364 ms 26888 KB Output is correct
5 Correct 386 ms 26820 KB Output is correct
6 Correct 403 ms 26940 KB Output is correct
7 Correct 376 ms 27132 KB Output is correct
8 Correct 403 ms 26916 KB Output is correct
9 Correct 364 ms 25576 KB Output is correct
10 Correct 319 ms 25552 KB Output is correct
11 Correct 179 ms 21984 KB Output is correct
12 Correct 378 ms 25784 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 27080 KB Output is correct
2 Correct 389 ms 27552 KB Output is correct
3 Correct 403 ms 27748 KB Output is correct
4 Correct 406 ms 26616 KB Output is correct
5 Correct 386 ms 27144 KB Output is correct
6 Correct 387 ms 29484 KB Output is correct
7 Correct 423 ms 30980 KB Output is correct
8 Correct 394 ms 27020 KB Output is correct
9 Correct 390 ms 27636 KB Output is correct
10 Correct 409 ms 27932 KB Output is correct
11 Correct 168 ms 23276 KB Output is correct
12 Correct 404 ms 30316 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10476 KB Output is correct
2 Correct 6 ms 8300 KB Output is correct
3 Correct 6 ms 8300 KB Output is correct
4 Correct 22 ms 12524 KB Output is correct
5 Correct 14 ms 10476 KB Output is correct
6 Correct 6 ms 8428 KB Output is correct
7 Correct 7 ms 8428 KB Output is correct
8 Correct 7 ms 8556 KB Output is correct
9 Correct 7 ms 8300 KB Output is correct
10 Correct 15 ms 10476 KB Output is correct
11 Correct 6 ms 8172 KB Output is correct
12 Correct 6 ms 8172 KB Output is correct
13 Correct 6 ms 8300 KB Output is correct
14 Correct 6 ms 8300 KB Output is correct
15 Correct 8 ms 8300 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 26944 KB Output is correct
2 Correct 368 ms 25864 KB Output is correct
3 Correct 392 ms 29664 KB Output is correct
4 Correct 364 ms 26888 KB Output is correct
5 Correct 386 ms 26820 KB Output is correct
6 Correct 403 ms 26940 KB Output is correct
7 Correct 376 ms 27132 KB Output is correct
8 Correct 403 ms 26916 KB Output is correct
9 Correct 364 ms 25576 KB Output is correct
10 Correct 319 ms 25552 KB Output is correct
11 Correct 179 ms 21984 KB Output is correct
12 Correct 378 ms 25784 KB Output is correct
13 Correct 383 ms 27080 KB Output is correct
14 Correct 389 ms 27552 KB Output is correct
15 Correct 403 ms 27748 KB Output is correct
16 Correct 406 ms 26616 KB Output is correct
17 Correct 386 ms 27144 KB Output is correct
18 Correct 387 ms 29484 KB Output is correct
19 Correct 423 ms 30980 KB Output is correct
20 Correct 394 ms 27020 KB Output is correct
21 Correct 390 ms 27636 KB Output is correct
22 Correct 409 ms 27932 KB Output is correct
23 Correct 168 ms 23276 KB Output is correct
24 Correct 404 ms 30316 KB Output is correct
25 Correct 15 ms 10476 KB Output is correct
26 Correct 6 ms 8300 KB Output is correct
27 Correct 6 ms 8300 KB Output is correct
28 Correct 22 ms 12524 KB Output is correct
29 Correct 14 ms 10476 KB Output is correct
30 Correct 6 ms 8428 KB Output is correct
31 Correct 7 ms 8428 KB Output is correct
32 Correct 7 ms 8556 KB Output is correct
33 Correct 7 ms 8300 KB Output is correct
34 Correct 15 ms 10476 KB Output is correct
35 Correct 6 ms 8172 KB Output is correct
36 Correct 6 ms 8172 KB Output is correct
37 Correct 6 ms 8300 KB Output is correct
38 Correct 6 ms 8300 KB Output is correct
39 Correct 8 ms 8300 KB Output is correct
40 Correct 326 ms 26492 KB Output is correct
41 Correct 356 ms 25632 KB Output is correct
42 Correct 357 ms 25876 KB Output is correct
43 Correct 200 ms 24300 KB Output is correct
44 Correct 198 ms 26220 KB Output is correct
45 Correct 394 ms 31528 KB Output is correct
46 Correct 385 ms 31304 KB Output is correct
47 Correct 362 ms 30288 KB Output is correct
48 Correct 210 ms 23276 KB Output is correct
49 Correct 297 ms 29820 KB Output is correct
50 Correct 382 ms 30872 KB Output is correct
51 Correct 392 ms 31572 KB Output is correct