제출 #1303771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303771		1ota	Aesthetic (NOI20_aesthetic)	C++20	13 / 100	2096 ms	100844 KiB

Aesthetic

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

using Edge = array<int, 3>;
const int inf = 1e18;

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<Edge> edge(m);
    for (auto& [u, v, w] : edge) cin >> u >> v >> w, u--, v--;

    vector<int> P(m);
    for (int i = m-2; i > -1; i--) P[i] = max(P[i+1], edge[i+1][2]);

    vector<int> S(n), T(n);
    vector<vector<pii>> G(n);
    for (auto [u, v, w] : edge) G[u].push_back({v, w}), G[v].push_back({u, w});

    auto dijkstra = [&](int s, vector<int>& dist){
        priority_queue<pii, vector<pii>, greater<pii>> pq; 
        fill(entire(dist), inf); pq.push(pii{0, s});
        while (!pq.empty()){
            auto [W, u] = pq.top(); pq.pop();
            if (dist[u] != inf) continue;
            else dist[u] = W;
            for (auto [v, w] : G[u]) pq.push(pii{W + w, v});
        }
    }; dijkstra(0, S); dijkstra(n-1, T);

    auto check = [&](int lim){
        bool good = false;
        vector<vector<Edge>> H(n); // H[u] -> { v, w, i }
        for (int i = 0; i < m; i++){
            auto [u, v, w] = edge[i];
            int dmin = min(S[u] + T[v], S[v] + T[u]) + w;
            if (dmin > lim) continue; good = true;
            H[u].push_back({v, w, i}); H[v].push_back({u, w, i});
        }

        if (!good) return true;

        int timer = 0;
        vector<bool> vis(n, false);
        vector<int> tin(n), tout(n), ei(n), pi(n);
        vector<vector<int>> adj(n);

        auto dfs = [&](auto&& self, int s, int parent, int idx) -> void{
            if (vis[s]) return;
            else vis[s] = true;
            ei[s] = idx, pi[s] = parent, tin[s] = timer++;
            for (auto [u, w, i] : H[s]) if (!vis[u]) {
                adj[s].push_back(u); self(self, u, s, i);
            } tout[s] = timer++;
        }; dfs(dfs, 0, 0, -1);

        vector<bool> bridge(m, false);
        vector<pii> dp(n, {inf, -1}); // minT, maxT
        auto dfsdp = [&](auto&& self, int s) -> bool{
            bool npi = (s == n-1);
            for (auto u : adj[s]){
                npi |= self(self, u);
                dp[s].ff = min(dp[u].ff, dp[s].ff);
                dp[s].ss = max(dp[u].ss, dp[s].ss);
            } for (auto [u, w, i] : H[s]) if (u != pi[s]){
                dp[s].ff = min(dp[s].ff, tin[u]);
                dp[s].ss = max(dp[s].ss, tin[u]);
            }
            if (pi[s] == s) return npi;
            if (!(tin[s] <= dp[s].ff and dp[s].ss <= tout[s])) return npi;
            else if (npi) bridge[ei[s]] = true;
            return npi;
        }; dfsdp(dfsdp, 0);

        for (int i = 0; i < m; i++) if (bridge[i]){
            auto [u, v, w] = edge[i];
            int dist = min(S[u] + T[v], S[v] + T[u]) + w + P[i];
            if (dist > lim) return true;
        }

        return false;
    };

    int low = 0, high = 1e12;
    while (low < high){
        int mid = (low + high + 1) / 2;
        if (check(mid)) low = mid;
        else high = mid-1;
    }

    cout << low + 1 << endl;

    return 0;
}

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