Submission #922977

#	Time	Username	Problem	Language	Result	Execution time	Memory
922977		vjudge1	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	146 ms	4040 KiB

ho_t4

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
    template <typename T1, typename T2>
    std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
    {
        in >> x.first >> x.second;
        return in;
    }

    template <typename T1, typename T2>
    std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
    {
        out << x.first << " " << x.second;
        return out;
    }

    template <typename T1>
    std::istream &operator>>(std::istream &in, std::vector<T1> &x)
    {
        for (auto &i : x)
            in >> i;
        return in;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e15) + 500;
const int BIG = (2e9) + 500;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

// #define int ll

struct test
{
    vector<vector<pll>> graph, invgraph;
    vector<int> components;
    int n, m;

    void merge(pll &a, ll val)
    {
        if (a.f > val)
        {
            a.s = a.f;
            a.f = val;
        }
        else
            a.s = min(a.s, val);
    }

    vector<int> used;
    void dijkstra(vector<ll> &dists, int st, int U, int V, ll C)
    {
        for (int i = 0; i < n; ++i)
            dists[i] = INF, used[i] = 0;
        dists[st] = 0;
        for (int i = 0; i < n; ++i)
        {
            int v = -1;
            for (int i = 0; i < n; ++i)
                if (!used[i] and (v == -1 or dists[v] > dists[i]))
                    v = i;
            if (v == -1)
                break;
            used[v] = 1;
            for (int i = 0; i < n; ++i)
                if (!used[i])
                {
                    ll cost;
                    if (U == v and V == i and graph[v][i].f == C)
                        cost = graph[v][i].s;
                    else
                        cost = graph[v][i].f;

                    if (U == i and V == v)
                        cost = min(cost, C);

                    dists[i] = min(dists[i], dists[v] + cost);
                }
        }
    }

    void invdijkstra(vector<ll> &dists, int st, int U, int V, ll C)
    {
        for (int i = 0; i < n; ++i)
            dists[i] = INF, used[i] = 0;
        dists[st] = 0;
        for (int i = 0; i < n; ++i)
        {
            int v = -1;
            for (int i = 0; i < n; ++i)
                if (!used[i] and (v == -1 or dists[v] > dists[i]))
                    v = i;
            if (v == -1)
                break;
            used[v] = 1;
            for (int i = 0; i < n; ++i)
                if (!used[i])
                {
                    ll cost = (U == v and V == i and invgraph[v][i].f == C ? invgraph[v][i].s : invgraph[v][i].f);
                    dists[i] = min(dists[i], dists[v] + cost);
                }
        }
    }

    vector<pii> E;
    vector<int> WAS;

    bool dfs(int v, int fn, vector<ll> &dist)
    {
        WAS[v] = 1;
        if (v == fn)
            return true;
        for (int tov = 0; tov < n; ++tov)
            if (!WAS[tov] and dist[v] == dist[tov] + graph[v][tov].f and dfs(tov, fn, dist))
            {
                E.pb({v, tov});
                return true;
            }
        return false;
    }

    void solve(int testcase)
    {
        boost();

        cin >> n >> m;

        WAS.resize(n);
        used.resize(n);
        graph.resize(n, vector<pll>(n, {INF, INF}));
        invgraph.resize(n, vector<pll>(n, {INF, INF}));

        vector<pair<pii, pii>> edges;

        for (int i = 0; i < m; ++i)
        {
            int v, tov, c, d;
            cin >> v >> tov >> c >> d;
            --v, --tov;
            merge(graph[v][tov], c);
            merge(invgraph[tov][v], c);
            edges.pb({{d, c}, {v, tov}});
        }
        sort(all(edges));

        vector<ll> dist0(n, INF), distN(n, INF), to0(n, INF), toN(n, INF);

        dijkstra(dist0, 0, 0, 0, 0);
        dijkstra(distN, n - 1, 0, 0, 0);
        invdijkstra(to0, 0, 0, 0, 0);
        invdijkstra(toN, n - 1, 0, 0, 0);

        vector<ll> bf(n);

        ll res = INF;
        if (dist0[n - 1] == INF and distN[n - 1] == INF)
        {
            for (auto [e1, e2] : edges)
            {
                auto [v, tov] = e2;
                auto [d, c] = e1;
                res = min(res, d + dist0[tov] + c + toN[v] + distN[tov] + c + to0[v]);
            }
        }
        else
        {
            map<pair<pii, ll>, ll> bad;

            int CC = 0;

            if (dist0[n - 1] != INF)
            {
                WAS.assign(n, 0);
                E.clear();
                assert(dfs(0, n - 1, toN));

                // reverse(all(E));
                // cout << E << " " << dist0[n - 1] << "!!\n";

                for (auto [v, tov] : E)
                {
                    CC++;
                    // if (CC > 2 * n + 10)
                    //     exit(0);
                    ll curRes = 0;
                    dijkstra(bf, 0, v, tov, graph[v][tov].f);
                    curRes += bf[n - 1];
                    dijkstra(bf, n - 1, v, tov, graph[v][tov].f);
                    curRes += bf[0];
                    bad[{{v, tov}, graph[v][tov].f}] = curRes;
                }
            }
            if (distN[0] != INF)
            {
                WAS.assign(n, 0);
                E.clear();
                assert(dfs(n - 1, 0, to0));

                // reverse(all(E));
                // cout << E << " " << distN[0] << "!!\n";

                for (auto [v, tov] : E)
                {
                    // if (CC > 2 * n + 10)
                    //     exit(0);
                    ll curRes = 0;
                    dijkstra(bf, 0, v, tov, graph[v][tov].f);
                    curRes += bf[n - 1];
                    dijkstra(bf, n - 1, v, tov, graph[v][tov].f);
                    curRes += bf[0];
                    bad[{{v, tov}, graph[v][tov].f}] = curRes;
                }
            }
            ll way0N = dist0[n - 1];
            ll wayN0 = distN[0];
            res = min(res, way0N + wayN0);

            for (auto [e1, e2] : edges)
            {
                auto [v, tov] = e2;
                auto [d, c] = e1;
                if (bad.find({{v, tov}, c}) != bad.end())
                    res = min(res, d + bad[{{v, tov}, c}]);
                else
                    res = min(res, d + min(way0N, dist0[tov] + c + toN[v]) + min(wayN0, distN[tov] + c + to0[v]));
            }
        }

        if (res == INF)
            cout << "-1\n";
        else
            cout << res << "\n";
    }
};

main()
{
    boost();
    int q = 1;
    // cin >> q;
    for (int i = 0; i < q; i++)
    {
        test t;
        t.solve(i);
    }
    return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
//                                                                                    //
//                               Coded by Der_Vlἀpos                                  //
//                                                                                    //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

Compilation message (stderr)

ho_t4.cpp:297:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  297 | main()
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63