oj.uz

Submission #203481

# Submission time Handle Problem Language Result Execution time Memory
203481 2020-02-20T22:22:49 Z tri Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 3828 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 = false;

    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 MAXV = 205;
const int MAXE = 5e4 + 10;
const ll INF = 1e15;

int V, E;

ll c[MAXE], r[MAXE];

struct graph {
    int u[MAXE], v[MAXE];

    int src;
    int sink;

    vi aL[MAXV];

    ll cost[MAXV];
    int pEdge[MAXV];

    vi sEdges;

    void dijkstra() {
        for (int i = 0; i < V; i++) {
            aL[i].clear();
        }
        for (int i = 0; i < E; i++) {
            aL[u[i]].pb(i);
        }

        fill(cost, cost + MAXV, INF);
        fill(pEdge, pEdge + MAXV, -1);
        sEdges.clear();

        priority_queue<pi, vector<pi>, greater<pi>> q;

        cost[src] = 0;
        q.push({0, src});

        while (!q.empty()) {
            pi st = q.top();
            q.pop();
            ll cC = st.f;
            int cV = st.s;

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

            for (int aE : aL[cV]) {
                assert(u[aE] == cV);
                int aV = v[aE];

                if (cost[aV] > cC + c[aE]) {
                    cost[aV] = cC + c[aE];
                    pEdge[aV] = aE;
                    q.push({cost[aV], aV});
                }
            }
        }

        int cV = sink;
        while (cV != src) {
            if (pEdge[cV] == -1) break;
            sEdges.pb(pEdge[cV]);
            cV = u[pEdge[cV]];
        }
    }
};

graph g1;
graph g2;

bool specEdge[MAXE];

ll partAns[MAXE];

// compute cost for all reversed edges from src to sink
void computeCost() {
    g1.dijkstra();

//    ps("fin1");

    fill(specEdge, specEdge + MAXE, false);
    for (int x : g1.sEdges) {
        specEdge[x] = true;
    }

    g2 = g1; // g2 is reverse graph
    for (int i = 0; i < E; i++) {
        swap(g2.u[i], g2.v[i]);
    }
    swap(g2.src, g2.sink);

    g2.dijkstra();
    assert(g1.cost[g1.sink] == g2.cost[g2.sink]);

//    ps("fin2");

    fill(partAns, partAns + MAXE, INF);

    for (int i = 0; i < E; i++) {
        if (g1.cost[g1.v[i]] < g1.cost[g1.u[i]]) { // edge is against gradient
            partAns[i] = g1.cost[g1.v[i]] + g2.cost[g1.u[i]] + c[i];
            partAns[i] = min(partAns[i], g1.cost[g1.sink]); // don't use reverse edge
        } else {
            if (specEdge) {
                graph g3 = g1;
                swap(g3.u[i], g3.v[i]);
                g3.dijkstra();

                partAns[i] = g3.cost[g3.sink];
            } else {
                partAns[i] = g1.cost[g1.sink]; // just use the already found shortest path
            }
        }
    }
}

ll ans[MAXE];

int main() {
    cin >> V >> E;

    for (int i = 0; i < E; i++) {
        cin >> g1.u[i] >> g1.v[i] >> c[i] >> r[i];
        g1.u[i]--, g1.v[i]--;
    }

    g1.src = 0;
    g1.sink = V - 1;

    computeCost();
    for (int i = 0; i < E; i++) {
        ans[i] = partAns[i] + r[i];
    }
    ans[E] = g1.cost[g1.sink];

//    ps("half");
//    ps(partAns[1]);

    swap(g1.src, g1.sink);

    computeCost();
    for (int i = 0; i < E; i++) {
        ans[i] += partAns[i];
    }
    ans[E] += g1.cost[g1.sink];
//
//    ps("full");
//    ps(partAns[1]);

    ll fAns = INF;
    for (int i = 0; i <= E; i++) {
        fAns = min(fAns, ans[i]);
    }

    assert(fAns >= 0);

    if (fAns == INF) {
        fAns = -1;
    }
    cout << fAns << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 1656 KB Output is correct
2 Correct 21 ms 1528 KB Output is correct
3 Correct 67 ms 1656 KB Output is correct
4 Correct 75 ms 1656 KB Output is correct
5 Correct 48 ms 1652 KB Output is correct
6 Correct 22 ms 1528 KB Output is correct
7 Correct 6 ms 1656 KB Output is correct
8 Correct 6 ms 1528 KB Output is correct
9 Correct 45 ms 1656 KB Output is correct
10 Correct 102 ms 1656 KB Output is correct
11 Correct 99 ms 1656 KB Output is correct
12 Correct 98 ms 1656 KB Output is correct
13 Correct 52 ms 1680 KB Output is correct
14 Correct 76 ms 1656 KB Output is correct
15 Correct 74 ms 1656 KB Output is correct
16 Correct 78 ms 1656 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 3828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 1656 KB Output is correct
2 Correct 23 ms 1528 KB Output is correct
3 Execution timed out 1087 ms 3448 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 1656 KB Output is correct
2 Correct 21 ms 1528 KB Output is correct
3 Correct 67 ms 1656 KB Output is correct
4 Correct 75 ms 1656 KB Output is correct
5 Correct 48 ms 1652 KB Output is correct
6 Correct 22 ms 1528 KB Output is correct
7 Correct 6 ms 1656 KB Output is correct
8 Correct 6 ms 1528 KB Output is correct
9 Correct 45 ms 1656 KB Output is correct
10 Correct 102 ms 1656 KB Output is correct
11 Correct 99 ms 1656 KB Output is correct
12 Correct 98 ms 1656 KB Output is correct
13 Correct 52 ms 1680 KB Output is correct
14 Correct 76 ms 1656 KB Output is correct
15 Correct 74 ms 1656 KB Output is correct
16 Correct 78 ms 1656 KB Output is correct
17 Execution timed out 1092 ms 3828 KB Time limit exceeded
18 Halted 0 ms 0 KB -