QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#273162#7883. Takeout Deliveringucup-team133#WA 180ms41996kbC++234.6kb2023-12-02 21:43:302023-12-02 21:43:30

Judging History

你现在查看的是最新测评结果

  • [2023-12-02 21:43:30]
  • 评测
  • 测评结果:WA
  • 用时:180ms
  • 内存:41996kb
  • [2023-12-02 21:43:30]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

struct UnionFind {
    UnionFind(int n) : n(n), num(n), data(n, -1) {}

    int find(int x) {
        assert(0 <= x && x < n);
        return data[x] < 0 ? x : data[x] = find(data[x]);
    }

    bool merge(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        if ((x = find(x)) == (y = find(y))) return false;
        if (-data[x] < -data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        num--;
        return true;
    }

    bool same(int x, int y) {
        assert(0 <= x && x < n);
        assert(0 <= y && y < n);
        return find(x) == find(y);
    }

    int size(int x) {
        assert(0 <= x && x < n);
        return -data[find(x)];
    }

    int count() const { return num; }

    std::vector<std::vector<int>> groups() {
        std::vector<std::vector<int>> res(n);
        for (int i = 0; i < n; i++) res[find(i)].emplace_back(i);
        res.erase(std::remove_if(res.begin(), res.end(), [&](const std::vector<int>& v) { return v.empty(); }));
        return res;
    }

    int operator[](int x) { return find(x); }

private:
    int n, num;
    // root node : -1 * component size
    // otherwise : parent
    std::vector<int> data;
};

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

struct edge {
    int u, v, w;
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator<(const edge& rhs) const { return w < rhs.w; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<edge> es;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        es.emplace_back(--u, --v, w);
    }

    sort(begin(es), end(es));
    UnionFind UF(n);
    int border = -1, threshold = -1;
    vector<vector<pair<int, int>>> G(n);
    for (int i = 0; i < m; i++) {
        auto [u, v, w] = es[i];
        UF.merge(u, v);
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
        if (UF.same(0, n - 1)) {
            border = i + 1;
            threshold = w;
            break;
        }
    }
    assert(border != -1);

    ll ans = IINF;
    {
        vector dp(n, vector<int>(2, INF));
        priority_queue<tuple<int, int, int>> pq;
        dp[0][0] = 0;
        pq.emplace(-dp[0][0], 0, 0);
        while (not pq.empty()) {
            auto [cost, v, x] = pq.top();
            pq.pop();
            cost *= -1;
            if (dp[v][x] != cost) continue;
            for (auto [u, w] : G[v]) {
                int nx = x, ncost = cost;
                if (x == 0 and w == threshold) {
                    nx++;
                } else
                    chmax(cost, w);
                if (chmin(dp[u][nx], ncost)) pq.emplace(-dp[u][nx], u, nx);
            }
        }
        ans = dp[n - 1][1] + threshold;
    }
    {
        auto calc = [&](int s) -> vector<int> {
            vector<int> dp(n, INF);
            priority_queue<pair<int, int>> pq;
            dp[s] = 0;
            pq.emplace(-dp[s], s);
            while (not pq.empty()) {
                auto [cost, v] = pq.top();
                pq.pop();
                cost *= -1;
                if (dp[v] != cost) continue;
                for (auto [u, w] : G[v]) {
                    if (chmin(dp[u], max(cost, w))) pq.emplace(-dp[u], u);
                }
            }
            return dp;
        };
        auto dp1 = calc(0), dp2 = calc(n - 1);
        for (int i = border; i < m; i++) {
            auto [u, v, w] = es[i];
            if (dp1[u] == INF) continue;
            if (dp2[v] == INF) continue;
            chmin(ans, w + max(dp1[u], dp2[v]));
        }
    }

    cout << ans << '\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3524kb

input:

4 6
1 2 2
1 3 4
1 4 7
2 3 1
2 4 3
3 4 9

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: -100
Wrong Answer
time: 180ms
memory: 41996kb

input:

300000 299999
80516 80517 597830404
110190 110191 82173886
218008 218009 954561262
250110 250111 942489774
66540 66541 156425292
34947 34948 239499776
273789 273790 453201232
84428 84429 439418398
98599 98600 326095035
55636 55637 355015760
158611 158612 684292473
43331 43332 43265001
171621 171622 ...

output:

1997532190

result:

wrong answer 1st numbers differ - expected: '1999991697', found: '1997532190'