Submission #719080

#	Time	Username	Problem	Language	Result	Execution time	Memory
719080		Cyanmond	Aesthetic (NOI20_aesthetic)	C++17	100 / 100	640 ms	96676 KiB

Aesthetic

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf64 = 1ll << 60;

struct Edge {
    int to;
    i64 cost;
    int id;
};

void solve() {
    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(M), B(M);
    std::vector<i64> W(M);
    std::vector<std::vector<Edge>> graph(N);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i] >> W[i];
        --A[i], --B[i];
        graph[A[i]].push_back({B[i], W[i], i});
        graph[B[i]].push_back({A[i], W[i], i});
    }
    std::vector<i64> C(M);
    for (int i = M - 2; i >= 0; --i) {
        C[i] = W[i + 1];
        C[i] = std::max(C[i], C[i + 1]);
    }

    auto calcMinDist = [&](const int f) {
        std::vector<i64> dist(N, inf64);
        std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> pq;
        dist[f] = 0;
        pq.push({0, f});
        while (not pq.empty()) {
            const auto [nowDist, v] = pq.top();
            pq.pop();
            if (nowDist > dist[v]) continue;
            for (const auto &[t, cost, id] : graph[v]) {
                const auto newDist = nowDist + cost;
                if (newDist < dist[t]) {
                    dist[t] = newDist;
                    pq.push({newDist, t});
                }
            }
        }
        return dist;
    };
    const auto dist1 = calcMinDist(0), dist2 = calcMinDist(N - 1);
    const auto minDist = dist1[N - 1];

    std::vector<int> edgeType(M);
    std::vector<std::vector<Edge>> sGraph(N);
    for (int i = 0; i < M; ++i) {
        if (dist1[A[i]] > dist1[B[i]]) std::swap(A[i], B[i]);
        const auto x = dist1[A[i]], y = dist2[B[i]];
        if (x + y + W[i] == minDist) {
            edgeType[i] = 1;
            sGraph[A[i]].push_back({B[i], W[i], i});
            sGraph[B[i]].push_back({A[i], W[i], i});
        }
    }
    std::vector<int> distX(N, -1);
    std::queue<int> que;
    distX[0] = 0;
    que.push(0);
    while (not que.empty()) {
        const auto f = que.front();
        que.pop();
        for (const auto &[t, cost, id] : sGraph[f]) {
            if (distX[t] == -1) {
                distX[t] = distX[f] + 1;
                que.push(t);
            }
        }
    }

    std::vector<bool> isSeen(N);
    std::vector<int> order(N), low(N), bridges;
    auto dfsLowlink = [&](auto &&self, const int v, const int p, int k) -> int {
        isSeen[v] = true;
        order[v] = k++;
        low[v] = order[v];
        for (const auto &[t, cost, id] : sGraph[v]) {
            if (not isSeen[t]) {
                k = self(self, t, v, k);
                low[v] = std::min(low[v], low[t]);
                if (order[v] < low[t]) bridges.push_back(id);
            } else if (t != p) {
                low[v] = std::min(low[v], order[t]);
            }
        }
        return k;
    };
    dfsLowlink(dfsLowlink, 0, -1, 0);
    std::sort(bridges.begin(), bridges.end(), [&](const int a, const int b) {
        const auto x = std::min(dist1[A[a]], dist1[B[a]]), y = std::min(dist1[A[b]], dist1[B[b]]);
        if (x != y) return x < y;
        const auto x2 = std::min(distX[A[a]], distX[B[a]]), y2 = std::min(distX[A[b]], distX[B[b]]);
        return x2 < y2;
    });
    std::vector<int> edgeId(M, -1);
    const int P = (int)bridges.size();
    for (int i = 0; i < P; ++i) {
        edgeId[bridges[i]] = i;
        edgeType[bridges[i]] = 2;
    }

    std::vector<i64> dist(N, inf64);
    std::vector<int> lastR(N, -1);
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    std::vector<std::vector<i64>> addEvent(P + 1), eraseEvent(P + 1);
    while (not pq.empty()) {
        const auto [nowDist, v] = pq.top();
        pq.pop();
        if (nowDist > dist[v]) continue;
        assert(nowDist == dist1[v]);
        for (const auto &[t, cost, id] : graph[v]) {
            const auto newDist = nowDist + cost;
            if (dist[t] > newDist) {
                dist[t] = newDist;
                pq.push({newDist, t});
            }
            const auto z = edgeId[id];
            const auto y = std::max({lastR[t], z, lastR[v]});
            if (newDist <= dist[t]) lastR[t] = y;
        }
    }
    auto eval = [&](int a, int b, i64 e, int u) {
        // if (dist[a] > dist[b]) return;
        const auto x = lastR[a], y = lastR[b];
        if (x >= y) return;
        addEvent[x + 1].push_back(dist[a] + e + dist2[b]);
        eraseEvent[y + 1 - u].push_back(dist[a] + e + dist2[b]);
    };
    for (int i = 0; i < M; ++i) {
        eval(A[i], B[i], W[i], edgeType[i] == 2 ? 1 : 0);
        eval(B[i], A[i], W[i], edgeType[i] == 2 ? 1 : 0);
    }

    std::multiset<i64> s;
    std::vector<i64> X(P);
    for (int i = 0; i < P; ++i) {
        for (const auto v : addEvent[i]) s.insert(v);
        for (const auto v : eraseEvent[i]) s.erase(s.find(v));
        X[i] = s.empty() ? inf64 : *s.begin();
    }
    i64 answer = minDist;
    for (int i = 0; i < P; ++i) {
        const auto x = minDist + C[bridges[i]], y = X[i];
        answer = std::max(answer, std::min(x, y));
    }
    std::cout << answer << std::endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    while (T--) {
        solve();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27