oj.uz

Submission #203482

# Submission time Handle Problem Language Result Execution time Memory
203482 2020-02-20T22:25:21 Z tri Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 2976 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;

int u[MAXE], v[MAXE];
ll c[MAXE], r[MAXE];

struct graph {

    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(u[i], v[i]);
    }
    swap(g2.src, g2.sink);

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

    for (int i = 0; i < E; i++) {
        swap(u[i], v[i]);
    }

//    ps("fin2");

    fill(partAns, partAns + MAXE, INF);

    for (int i = 0; i < E; i++) {
        if (g1.cost[v[i]] < g1.cost[u[i]]) { // edge is against gradient
            partAns[i] = g1.cost[v[i]] + g2.cost[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(u[i], v[i]);
                g3.dijkstra();
                swap(u[i], v[i]);

                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 >> u[i] >> v[i] >> c[i] >> r[i];
        u[i]--, 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 70 ms 888 KB Output is correct
2 Correct 10 ms 760 KB Output is correct
3 Correct 47 ms 888 KB Output is correct
4 Correct 51 ms 888 KB Output is correct
5 Correct 26 ms 888 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 764 KB Output is correct
9 Correct 20 ms 760 KB Output is correct
10 Correct 73 ms 888 KB Output is correct
11 Correct 68 ms 888 KB Output is correct
12 Correct 71 ms 888 KB Output is correct
13 Correct 31 ms 888 KB Output is correct
14 Correct 47 ms 888 KB Output is correct
15 Correct 44 ms 888 KB Output is correct
16 Correct 49 ms 888 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 892 KB Output is correct
2 Correct 11 ms 888 KB Output is correct
3 Execution timed out 1094 ms 2432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 888 KB Output is correct
2 Correct 10 ms 760 KB Output is correct
3 Correct 47 ms 888 KB Output is correct
4 Correct 51 ms 888 KB Output is correct
5 Correct 26 ms 888 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 764 KB Output is correct
9 Correct 20 ms 760 KB Output is correct
10 Correct 73 ms 888 KB Output is correct
11 Correct 68 ms 888 KB Output is correct
12 Correct 71 ms 888 KB Output is correct
13 Correct 31 ms 888 KB Output is correct
14 Correct 47 ms 888 KB Output is correct
15 Correct 44 ms 888 KB Output is correct
16 Correct 49 ms 888 KB Output is correct
17 Execution timed out 1091 ms 2976 KB Time limit exceeded
18 Halted 0 ms 0 KB -