Submission #923139

#	Time	Username	Problem	Language	Result	Execution time	Memory
923139		Camillus	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	787 ms	6504 KiB

ho_t4

/// @author Camillus
#include <bits/stdc++.h>
#define int long long

using ll = long long;
using namespace std;

int from[50'000];
int to[50'000];
int cost[50'000];
int change[50'000];

static constexpr int INF = 1e17;

int n, m;

vector<pair<int, int>> g[200];
int d_from[200];
int d_to[200];

vector<int> shuffled;

void dist_from_all(int s) {
    for (int u = 0; u < n; u++) {
        g[u].resize(0);
    }

    for (int i : shuffled) {
        g[to[i]].emplace_back(from[i], cost[i]);
    }

    auto d = d_to;
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    d[s] = 0;

    set<pair<int, int>> Q;
    Q.emplace(d[s], s);

    while (!Q.empty()) {
        int u = Q.begin()->second;
        Q.erase(Q.begin());

        for (auto [v, c] : g[u]) {
            if (d[v] > d[u] + c) {
                Q.erase(pair(d[v], v));
                d[v] = d[u] + c;
                Q.emplace(d[v], v);
            }
        }
    }
}

void dist_to_all(int s) {
    for (int u = 0; u < n; u++) {
        g[u].resize(0);
    }

    for (int i : shuffled) {
        g[from[i]].emplace_back(to[i], cost[i]);
    }

    auto d = d_from;
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    d[s] = 0;

    set<pair<int, int>> Q;
    Q.emplace(d[s], s);

    while (!Q.empty()) {
        int u = Q.begin()->second;
        Q.erase(Q.begin());

        for (auto [v, c] : g[u]) {
            if (d[v] > d[u] + c) {
                Q.erase(pair(d[v], v));
                d[v] = d[u] + c;
                Q.emplace(d[v], v);
            }
        }
    }
}

int get_cost() {
    int result = 0;

    dist_to_all(0);
    dist_from_all(0);

    return min(INF, d_from[n - 1] + d_to[n - 1]);
}

random_device rd;
mt19937_64 rnd(rd());

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;

    shuffled.resize(m);
    iota(shuffled.begin(), shuffled.end(), 0);
    shuffle(shuffled.begin(), shuffled.end(), rnd);

    for (int i = 0; i < m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        u--, v--;

        from[i] = u;
        to[i] = v;
        cost[i] = c;
        change[i] = d;
    }

    auto group1 = [&]() -> bool {
        return m <= 1000;
    };

    auto group2 = [&]() -> bool {
        if (m % 2 == 1) {
            return false;
        }

        for (int i = 0; i < m; i += 2) {
            bool condition = from[i] == from[i + 1] && to[i] == to[i + 1] && cost[i] == cost[i + 1];
            if (!condition) {
                return false;
            }
        }

        return true;
    };

    auto group3 = [&]() -> bool {
        for (int i = 0; i < m; i++) {
            if (cost[i] != 0) {
                return false;
            }
        }
        return true;
    };

    vector<vector<int>> d(n, vector<int>(n, INF));
    vector<int> good;

    for (int i = 0; i < m; i++) {
        d[from[i]][to[i]] = min(d[from[i]][to[i]], cost[i]);
    }

    for (int u = 0; u < n; u++) {
        d[u][u] = 0;
    }

    for (int k = 0; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                d[u][v] = min(d[u][v], d[u][k] + d[k][v]);
            }
        }
    }

    vector<int> best1(m);
    iota(best1.begin(), best1.end(), 0);
    sort(best1.begin(), best1.end(), [&](int i, int j) -> bool {
        auto val = [&](int x) -> int {
            return d[0][to[x]] + cost[x] + change[x] + d[from[x]][n - 1];
        };
        return val(i) < val(j);
    });
    best1.resize(min(best1.size(), (size_t)100));

    vector<int> best2(m);
    iota(best2.begin(), best2.end(), 0);
    sort(best2.begin(), best2.end(), [&](int i, int j) -> bool {
        auto val = [&](int x) -> int {
            return d[n - 1][to[x]] + cost[x] + change[x] + d[from[x]][0];
        };
        return val(i) < val(j);
    });
    best2.resize(min(best2.size(), (size_t)100));

    vector<int> best;
    for (int i : best1) {
        best.push_back(i);
    }
    for (int i : best2) {
        best.push_back(i);
    }

    sort(best.begin(), best.end());
    best.erase(unique(best.begin(), best.end()), best.end());

    int initial = get_cost();
    int ans = initial;

    for (int i : best) {
        swap(from[i], to[i]);
        ans = min(ans, get_cost() + change[i]);
        swap(from[i], to[i]);
    }

    cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'long long int get_cost()':
ho_t4.cpp:88:9: warning: unused variable 'result' [-Wunused-variable]
   88 |     int result = 0;
      |         ^~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:119:10: warning: variable 'group1' set but not used [-Wunused-but-set-variable]
  119 |     auto group1 = [&]() -> bool {
      |          ^~~~~~
ho_t4.cpp:123:10: warning: variable 'group2' set but not used [-Wunused-but-set-variable]
  123 |     auto group2 = [&]() -> bool {
      |          ^~~~~~
ho_t4.cpp:138:10: warning: variable 'group3' set but not used [-Wunused-but-set-variable]
  138 |     auto group3 = [&]() -> bool {
      |          ^~~~~~

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