Submission #1187904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187904		patgra	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	247 ms	9884 KiB

ho_t4

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back
#define int ll

using namespace std;

constexpr int inf = 1e18 + 7;
int n, m;
vector<array<int, 4>> edges;
vector<pair<int, int>> whichEdge;
vector<vector<pair<int, int>>> g, gR;
vector<vector<vector<int>>> dist; // from 1, from N, to 1, to N
vector<vector<vector<int>>> minPref, minSuf;

void calcDistWithout(int X, int S, int which, bool rev) {
    vector<bool> vis(n + 1, 0);
    rep(i, 1, n + 1) dist[which][X][i] = inf;
    dist[which][X][S] = 0;
    int squirt = (int)sqrt(n);
    vector<pair<int, int>> sqAr((n + 1) / squirt + 1, {inf, inf});
    sqAr[S / squirt] = {0, S};
    while(true) {
        pair<int, int> minDist = {inf, inf};
        repIn(i, sqAr) minDist = min(minDist, i);
        auto [ds, v] = minDist;
        if(ds == inf) break;
        vis[v] = true;
        sqAr[v / squirt] = {inf, inf};
        int mysq = v / squirt;
        rep(i, mysq * squirt, min(mysq * squirt + squirt, n + 1)) if(!vis[i]) sqAr[mysq] = min(sqAr[mysq], {dist[which][X][i], i});
        if(v == X) continue;
        repIn2(u, d, (rev ? gR : g)[v]) if(!vis[u]) dist[which][X][u] = min(dist[which][X][u], ds + d), sqAr[u / squirt] = min(sqAr[u / squirt], {ds + d, u});
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m;
    edges.resize(m);
    whichEdge.resize(m);
    g.resize(n + 1);gR.resize(n + 1);
    dist.resize(4, vector<vector<int>>(n + 1, vector<int>(n + 1)));
    minPref.resize(4, vector<vector<int>>(n + 1));
    minSuf.resize(4, vector<vector<int>>(n + 1));
    rep(i, 0, m) {
        int v, u, c1, c2;
        cin >> v >> u >> c1 >> c2;
        edges[i] = {v, u, c1, c2};
        whichEdge[i] = {g[v].size(), gR[u].size()};
        g[v].pb({u, c1});
        gR[u].pb({v, c1});
    }
    
    rep(i, 1, n + 1) calcDistWithout(i, 1, 0, 0);
    rep(i, 1, n + 1) calcDistWithout(i, n, 1, 0);
    rep(i, 1, n + 1) calcDistWithout(i, 1, 2, 1);
    rep(i, 1, n + 1) calcDistWithout(i, n, 3, 1);
    DEBUG {
        DC << "Dist from 1: " << eol;
        rep(i, 1, n + 1) {
            DC << " without " << i << ": " << eol;
            rep(j, 1, n + 1) DC << "  (" << j << "): " << dist[0][i][j] << eol;
        }
        DC << "Dist from N: " << eol;
        rep(i, 1, n + 1) {
            DC << " without " << i << ": " << eol;
            rep(j, 1, n + 1) DC << "  (" << j << "): " << dist[1][i][j] << eol;
        }
        DC << "Dist to 1: " << eol;
        rep(i, 1, n + 1) {
            DC << " without " << i << ": " << eol;
            rep(j, 1, n + 1) DC << "  (" << j << "): " << dist[2][i][j] << eol;
        }
        DC << "Dist to N: " << eol;
        rep(i, 1, n + 1) {
            DC << " without " << i << ": " << eol;
            rep(j, 1, n + 1) DC << "  (" << j << "): " << dist[3][i][j] << eol;
        }
    }

    rep(which, 0, 4) rep(v, 1, n + 1) { 
        minPref[which][v].resize(g[v].size());
        int mp = inf;
        int i = 0;
        repIn2(u, c, g[v]) { 
            mp = min(mp, c + dist[which][v][u]);
            minPref[which][v][i++] = mp;
        }
    }
    rep(which, 0, 4) rep(v, 1, n + 1) {
        minSuf[which][v].resize(g[v].size());
        int mp = inf;
        int i = (int)g[v].size() - 1;
        ranges::reverse(g[v]);
        repIn2(u, c, g[v]) { 
            mp = min(mp, c + dist[which][v][u]);
            minSuf[which][v][i--] = mp;
        }
        ranges::reverse(g[v]);
    }

    int ans = min(inf, dist[0][n][n] + dist[1][1][1]);
    DC << "if we reverse nothing ans = " << ans << eol;
    int i = 0;
    for(auto [v, u, c1, c2] : edges) {
        auto [ii, ir] = whichEdge[i];
        int toN = min(dist[0][v][n], dist[0][v][v] + min((ii ? minPref[3][v][ii - 1] : inf), (ii < (int)g[v].size() - 1 ? minSuf[3][v][ii + 1] : inf)));
        toN = min(toN, dist[0][v][u] + c1 + dist[3][u][v]);
        int fromN = min(dist[1][v][1], dist[1][v][v] + min((ii ? minPref[2][v][ii - 1] : inf), (ii < (int)g[v].size() - 1 ? minSuf[2][v][ii + 1] : inf)));
        fromN = min(fromN, dist[1][v][u] + c1 + dist[2][u][v]);
        DC << "if we reverse edge " << i << " ans = " << toN + fromN + c2 << eol;
        ans = min(ans, toN + fromN + c2);
        i++;
    }

    cout << (ans == inf ? -1 : ans) << '\n';
}

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