oj.uz

Submission #857243

# Submission time Handle Problem Language Result Execution time Memory
857243 2023-10-05T16:06:53 Z quanlt206 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 245 ms 23880 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div

using namespace std;

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<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

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;
    }
/* END OF TEMPLATE */

const int N = 1e5 + 7;

vector<pii> v[N];

ll d[4][N];

int n, m, s, t, x, y;

void dijkstra(ll d[], int s) {
    FOR(i, 1, n) d[i] = 1e18;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    d[s] = 0;
    pq.push({d[s], s});
    while (!pq.empty()) {
        pli tmp = pq.top();
        pq.pop();
        ll w = tmp.X;
        int u = tmp.Y;
        if (w != d[u]) continue;
        for (auto x : v[u])
            if (minimize(d[x.X], w + x.Y)) pq.push({d[x.X], x.X});
    }
}

ll f[N], g[N];
int deg[N];
vector<int> adj[N];
bool onRoute[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s>>t>>x>>y;
    FOR(i, 1, m) {
        int x, y, c;
        cin>>x>>y>>c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    dijkstra(d[0], s);
    dijkstra(d[1], t);
    dijkstra(d[2], x);
    dijkstra(d[3], y);
    FOR(i, 1, n)
        if (d[0][i] + d[1][i] == d[0][t]) onRoute[i] = true;
    FOR(x, 1, n)
        for (auto y : v[x])
            if (d[0][x] + y.Y == d[0][y.X]) {
                adj[x].push_back(y.X);
                deg[y.X]++;
            }
    ////  Topo
    vector<int> T;
    queue<int> qu;
    FOR(i, 1, n)
        if (deg[i] == 0) qu.push(i);
    while (!qu.empty()) {
        int x = qu.front();
        qu.pop();
        T.push_back(x);
        for (auto y : adj[x])
            if (--deg[y] == 0) qu.push(y);
    }
    reverse(all(T));
    for (auto x : T) {
        f[x] = g[x] = 1e18;
        if (onRoute[x]) f[x] = d[2][x], g[x] = d[3][x];
        for (auto y : adj[x]) {
            minimize(f[x], f[y]);
            minimize(g[x], g[y]);
        }
    }
    ll res = d[2][y];
    FOR(i, 1, n)
        if (onRoute[i]) {
            minimize(res, d[2][i] + g[i]);
            minimize(res, d[3][i] + f[i]);
        }
    cout<<res;
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 19572 KB Output is correct
2 Correct 175 ms 19392 KB Output is correct
3 Correct 196 ms 22192 KB Output is correct
4 Correct 189 ms 21404 KB Output is correct
5 Correct 162 ms 21920 KB Output is correct
6 Correct 202 ms 21976 KB Output is correct
7 Correct 188 ms 22144 KB Output is correct
8 Correct 185 ms 22000 KB Output is correct
9 Correct 163 ms 21152 KB Output is correct
10 Correct 139 ms 20940 KB Output is correct
11 Correct 71 ms 18344 KB Output is correct
12 Correct 189 ms 21944 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 19036 KB Output is correct
2 Correct 214 ms 19036 KB Output is correct
3 Correct 177 ms 19152 KB Output is correct
4 Correct 208 ms 19432 KB Output is correct
5 Correct 194 ms 19172 KB Output is correct
6 Correct 186 ms 19964 KB Output is correct
7 Correct 245 ms 20048 KB Output is correct
8 Correct 185 ms 19152 KB Output is correct
9 Correct 242 ms 19216 KB Output is correct
10 Correct 197 ms 19212 KB Output is correct
11 Correct 70 ms 17116 KB Output is correct
12 Correct 179 ms 20072 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10844 KB Output is correct
2 Correct 2 ms 10276 KB Output is correct
3 Correct 2 ms 10072 KB Output is correct
4 Correct 12 ms 11608 KB Output is correct
5 Correct 7 ms 11100 KB Output is correct
6 Correct 3 ms 10332 KB Output is correct
7 Correct 3 ms 10260 KB Output is correct
8 Correct 3 ms 10584 KB Output is correct
9 Correct 3 ms 10332 KB Output is correct
10 Correct 7 ms 11092 KB Output is correct
11 Correct 2 ms 10076 KB Output is correct
12 Correct 2 ms 10264 KB Output is correct
13 Correct 3 ms 10076 KB Output is correct
14 Correct 3 ms 10256 KB Output is correct
15 Correct 2 ms 10076 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 19572 KB Output is correct
2 Correct 175 ms 19392 KB Output is correct
3 Correct 196 ms 22192 KB Output is correct
4 Correct 189 ms 21404 KB Output is correct
5 Correct 162 ms 21920 KB Output is correct
6 Correct 202 ms 21976 KB Output is correct
7 Correct 188 ms 22144 KB Output is correct
8 Correct 185 ms 22000 KB Output is correct
9 Correct 163 ms 21152 KB Output is correct
10 Correct 139 ms 20940 KB Output is correct
11 Correct 71 ms 18344 KB Output is correct
12 Correct 189 ms 21944 KB Output is correct
13 Correct 190 ms 19036 KB Output is correct
14 Correct 214 ms 19036 KB Output is correct
15 Correct 177 ms 19152 KB Output is correct
16 Correct 208 ms 19432 KB Output is correct
17 Correct 194 ms 19172 KB Output is correct
18 Correct 186 ms 19964 KB Output is correct
19 Correct 245 ms 20048 KB Output is correct
20 Correct 185 ms 19152 KB Output is correct
21 Correct 242 ms 19216 KB Output is correct
22 Correct 197 ms 19212 KB Output is correct
23 Correct 70 ms 17116 KB Output is correct
24 Correct 179 ms 20072 KB Output is correct
25 Correct 7 ms 10844 KB Output is correct
26 Correct 2 ms 10276 KB Output is correct
27 Correct 2 ms 10072 KB Output is correct
28 Correct 12 ms 11608 KB Output is correct
29 Correct 7 ms 11100 KB Output is correct
30 Correct 3 ms 10332 KB Output is correct
31 Correct 3 ms 10260 KB Output is correct
32 Correct 3 ms 10584 KB Output is correct
33 Correct 3 ms 10332 KB Output is correct
34 Correct 7 ms 11092 KB Output is correct
35 Correct 2 ms 10076 KB Output is correct
36 Correct 2 ms 10264 KB Output is correct
37 Correct 3 ms 10076 KB Output is correct
38 Correct 3 ms 10256 KB Output is correct
39 Correct 2 ms 10076 KB Output is correct
40 Correct 187 ms 23880 KB Output is correct
41 Correct 185 ms 22644 KB Output is correct
42 Correct 168 ms 22760 KB Output is correct
43 Correct 62 ms 19152 KB Output is correct
44 Correct 63 ms 19368 KB Output is correct
45 Correct 192 ms 23560 KB Output is correct
46 Correct 157 ms 23304 KB Output is correct
47 Correct 211 ms 23268 KB Output is correct
48 Correct 64 ms 18756 KB Output is correct
49 Correct 148 ms 23428 KB Output is correct
50 Correct 228 ms 23316 KB Output is correct
51 Correct 208 ms 23444 KB Output is correct