oj.uz

Submission #202201

# Submission time Handle Problem Language Result Execution time Memory
202201 2020-02-14T06:15:29 Z tri Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 928 ms 34884 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


const int MAXN = 1e5 + 10;
const ll INF = 1e15;

vector<pi> aL[MAXN];
vector<pi> sL[MAXN];

vector<pi> pre[MAXN];

int N, M;
int S, T, U, V;

// finds DAG for routes from S to T, adds directed edges to sL

void fOPath() {
    ll cost[MAXN];
    fill(cost, cost + MAXN, INF);
    cost[S] = 0;

    priority_queue<pl, vector<pl>, greater<pl>> q;
    q.push({0, S});

    while (q.size()) {
        auto cS = q.top();
        q.pop();

        int cV = cS.s;
        ll cC = cS.f;

        if (cost[cV] < cC) {
            continue;
        }

        for (pi aE : aL[cV]) {
            int aV = aE.f;
            ll eC = aE.s;

            if (cC + eC < cost[aV]) {
                cost[aV] = cC + eC;
                pre[aV].clear();
                pre[aV].pb({cV, eC});

                q.push({cC + eC, aV});
            } else if (cC + eC == cost[aV]) {
                pre[aV].pb({cV, eC});
            }
        }
    }

    queue<int> q2;

    bool inQ2[MAXN];
    fill(inQ2, inQ2 + MAXN, false);

    inQ2[T] = true;
    q2.push(T);

    while (q2.size()) {
        int cV = q2.front();
        q2.pop();

        for (pi preE : pre[cV]) {
            if (!inQ2[preE.f]) {
                q2.push(preE.f);
                inQ2[preE.f] = true;
            }
            sL[preE.f].pb({cV, 0});

//            ps(preE.f, "->", cV);
        }
    }
}

// state depends on cV and whether we've used, are using, or haven't used the special edges
ll dp[MAXN][3];

// given aL and sL, finds best route
ll fBest() {
    priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> q;

    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = INF;
        }
    }

    q.push({0, {U, 0}});
    dp[U][0] = 0;

    while (q.size()) {
        auto cS = q.top();
        q.pop();

        ll cC = cS.f;
        int cV = cS.s.f;
        int cCond = cS.s.s;

        if (dp[cV][cCond] < cC) {
            continue;
        }

        // normal transitions
        for (pi aE : aL[cV]) {
            int aV = aE.f;
            ll eC = aE.s;
            int nCond = cCond == 0 ? 0 : 2;

            if (dp[aV][nCond] > cC + eC) {
                dp[aV][nCond] = cC + eC;
                q.push({cC + eC, {aV, nCond}});
            }
        }

        // special transitions
        if (cCond != 2) {
            for (pi aE : sL[cV]) {
                int aV = aE.f;
                ll eC = aE.s;
                int nCond = 1;

                if (dp[aV][nCond] > cC + eC) {
                    dp[aV][nCond] = cC + eC;
                    q.push({cC + eC, {aV, nCond}});
                }
            }
        }
    }
    return min(min(dp[V][0], dp[V][1]), dp[V][2]);
}

int main() {
    cin >> N >> M;
    cin >> S >> T >> U >> V;
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        aL[A].pb({B, C});
        aL[B].pb({A, C});
    }
    fOPath();

    ll a1 = fBest();
    swap(U, V);

    ll a2 = fBest();

    ll ans = min(a1, a2);

    cout << ans << endl;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 25740 KB Output is correct
2 Correct 748 ms 24528 KB Output is correct
3 Correct 844 ms 29004 KB Output is correct
4 Correct 658 ms 26016 KB Output is correct
5 Correct 747 ms 25728 KB Output is correct
6 Correct 660 ms 25936 KB Output is correct
7 Correct 792 ms 25644 KB Output is correct
8 Correct 781 ms 25484 KB Output is correct
9 Correct 711 ms 22496 KB Output is correct
10 Correct 619 ms 22744 KB Output is correct
11 Correct 385 ms 22148 KB Output is correct
12 Correct 754 ms 27068 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 24468 KB Output is correct
2 Correct 755 ms 24236 KB Output is correct
3 Correct 740 ms 24224 KB Output is correct
4 Correct 769 ms 24292 KB Output is correct
5 Correct 729 ms 24420 KB Output is correct
6 Correct 823 ms 28472 KB Output is correct
7 Correct 734 ms 25292 KB Output is correct
8 Correct 740 ms 24308 KB Output is correct
9 Correct 731 ms 24504 KB Output is correct
10 Correct 753 ms 24292 KB Output is correct
11 Correct 429 ms 22296 KB Output is correct
12 Correct 837 ms 28916 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11640 KB Output is correct
2 Correct 14 ms 10616 KB Output is correct
3 Correct 13 ms 10616 KB Output is correct
4 Correct 69 ms 12152 KB Output is correct
5 Correct 39 ms 11384 KB Output is correct
6 Correct 13 ms 10616 KB Output is correct
7 Correct 15 ms 10744 KB Output is correct
8 Correct 16 ms 10744 KB Output is correct
9 Correct 14 ms 10744 KB Output is correct
10 Correct 40 ms 11256 KB Output is correct
11 Correct 12 ms 10616 KB Output is correct
12 Correct 12 ms 10616 KB Output is correct
13 Correct 13 ms 10616 KB Output is correct
14 Correct 13 ms 10616 KB Output is correct
15 Correct 13 ms 10616 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 25740 KB Output is correct
2 Correct 748 ms 24528 KB Output is correct
3 Correct 844 ms 29004 KB Output is correct
4 Correct 658 ms 26016 KB Output is correct
5 Correct 747 ms 25728 KB Output is correct
6 Correct 660 ms 25936 KB Output is correct
7 Correct 792 ms 25644 KB Output is correct
8 Correct 781 ms 25484 KB Output is correct
9 Correct 711 ms 22496 KB Output is correct
10 Correct 619 ms 22744 KB Output is correct
11 Correct 385 ms 22148 KB Output is correct
12 Correct 754 ms 27068 KB Output is correct
13 Correct 716 ms 24468 KB Output is correct
14 Correct 755 ms 24236 KB Output is correct
15 Correct 740 ms 24224 KB Output is correct
16 Correct 769 ms 24292 KB Output is correct
17 Correct 729 ms 24420 KB Output is correct
18 Correct 823 ms 28472 KB Output is correct
19 Correct 734 ms 25292 KB Output is correct
20 Correct 740 ms 24308 KB Output is correct
21 Correct 731 ms 24504 KB Output is correct
22 Correct 753 ms 24292 KB Output is correct
23 Correct 429 ms 22296 KB Output is correct
24 Correct 837 ms 28916 KB Output is correct
25 Correct 42 ms 11640 KB Output is correct
26 Correct 14 ms 10616 KB Output is correct
27 Correct 13 ms 10616 KB Output is correct
28 Correct 69 ms 12152 KB Output is correct
29 Correct 39 ms 11384 KB Output is correct
30 Correct 13 ms 10616 KB Output is correct
31 Correct 15 ms 10744 KB Output is correct
32 Correct 16 ms 10744 KB Output is correct
33 Correct 14 ms 10744 KB Output is correct
34 Correct 40 ms 11256 KB Output is correct
35 Correct 12 ms 10616 KB Output is correct
36 Correct 12 ms 10616 KB Output is correct
37 Correct 13 ms 10616 KB Output is correct
38 Correct 13 ms 10616 KB Output is correct
39 Correct 13 ms 10616 KB Output is correct
40 Correct 692 ms 30784 KB Output is correct
41 Correct 699 ms 25724 KB Output is correct
42 Correct 705 ms 25736 KB Output is correct
43 Correct 489 ms 24296 KB Output is correct
44 Correct 462 ms 24456 KB Output is correct
45 Correct 877 ms 31720 KB Output is correct
46 Correct 780 ms 33064 KB Output is correct
47 Correct 706 ms 30216 KB Output is correct
48 Correct 448 ms 23916 KB Output is correct
49 Correct 643 ms 31196 KB Output is correct
50 Correct 867 ms 33020 KB Output is correct
51 Correct 928 ms 34884 KB Output is correct