Submission #1126581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126581		underwaterkillerwhale	Aesthetic (NOI20_aesthetic)	C++20	22 / 100	868 ms	151252 KiB

Aesthetic

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 3e5 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 450;

struct Edge {
    int u, v, w;
};

int n, m;
vector<pii> ke[N];
vector<int> adj[N], adj2[N];
ll dp[2][N];

int low[N], num[N], dd[N], cpn[N];
int high[N];
ll spt2[N][25];
int par[N][25];

void solution() {
    cin >> n >> m;
    vector<Edge> edges;
    rep (i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        ke[u].pb({v, w});
        ke[v].pb({u, w});
        edges.pb({u, v, w});
    }
    memset(dp, 0x3f, sizeof dp);
    auto Dijkstra = [&] (int st, int typ) {
        vector<int> vis(n + 3, 0);
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        pq.push({0, st});
        dp[typ][st] = 0;
        while (!pq.empty()) {
            int u = pq.top().se;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            iter (&id, ke[u]) {
                int v = id.fs, w = id.se;
                if (dp[typ][v] > dp[typ][u] + w) {
                    dp[typ][v] = dp[typ][u] + w;
                    pq.push({dp[typ][v], v});
                }
            }
        }
    };
    Dijkstra(1, 0);
    Dijkstra(n, 1);
    rep (u, 1, n) {
        iter (&id, ke[u]) {
            int v, w;
            tie(v, w) = id;
            if (dp[0][u] + w == dp[0][v]) {
//                cout << u <<" "<<v<<" a\n";
                adj[u].pb(v);
                adj[v].pb(u);
            }
        }
    }
    stack<int> st;
    int num_cpn = 0;
    function<void(int, int)> dfs = [&] (int u, int p) {
        static int time_dfs = 0;
        num[u] = low[u] = ++time_dfs;
        st.push(u);
        iter (&v, adj[u]) {
            if (v == p) continue;
            if (!num[v]) {
                adj2[u].pb(v);
//                cout << u <<" "<<v<<"\n";
                dfs(v, u);
                low[u] = min(low[u], low[v]);
            }
            else low[u] = min(low[u], num[v]);
        }
//            cout << u <<" "<<dp[0][u] <<" "<<dp[1][u] <<" asdasdasd\n";
        if (low[u] == num[u]) {
            if (dp[0][u] + dp[1][u] == dp[0][n] && p != 0)
            dd[u] = 1;
            ++num_cpn;
            int v;
            do {
                v = st.top();
                cpn[v] = num_cpn;
                st.pop();
            }while(v != u);
        }
    };

    dfs(1, 0);
    function<void(int, int)> dfs2 = [&] (int u, int p) {
        par[u][0] = p;
        high[u] = high[p] + 1;
        rep (i, 1, 20) {
            par[u][i] = par[par[u][i - 1]][i - 1];
        }
        iter (&v, adj2[u]) {
            if (v != p) {
                dfs2(v, u);
            }
        }
    };
    dfs2(1, 0);
    auto LCA = [&] (int u, int v) {
        if (high[u] > high[v]) swap(u, v);
        rep (i, 0, 20) if (bit(high[v] - high[u], i)) v = par[v][i];
        if (v == u) return u;
        REB (i, 20, 0) if (par[v][i] != par[u][i]) {
            v = par[v][i];
            u = par[u][i];
        }
        return par[u][0];
    };

    memset(spt2, 0x3f, sizeof spt2);

    auto Jump = [&] (int u, int delta, ll Cost) {
        if (delta <= 0) return;
//        cout << u <<" "<<delta <<" "<<Cost <<" ffff\n";
        rep (i, 0, 20) {
            if (bit(delta, i)) {
                spt2[u][i] = min(spt2[u][i], Cost);
                u = par[u][i];
            }
        }
    };

    auto Update = [&] (int u, int v, ll Cost) {
        int anc = LCA(u, v);
        Jump (u, high[u] - high[anc], Cost);
        Jump (v, high[v] - high[anc], Cost);
    };

    REB (i, 20, 1) {
        rep (u, 1, n) {
            spt2[u][i - 1] = min(spt2[u][i - 1], spt2[u][i]);
            spt2[par[u][i - 1]][i - 1] = min(spt2[par[u][i - 1]][i - 1], spt2[u][i]);
        }
    }
    vector<int> suf(m + 3, 0);
    REB (i, m - 1, 0) {
        suf[i] = max(suf[i + 1], edges[i].w);
    }
    rep (i, 0, m - 1) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (dp[0][u] > dp[0][v]) swap(u, v);
        int add = dp[0][u] + dp[1][v] + w == dp[0][n] ? suf[i + 1] : 0;
        ll Cost = dp[0][u] + dp[1][v] + add + w;
//        cout << u << " "<<v<<" "<<Cost <<" asd\n";
        Update (u, v, Cost);
    }
    ll res = dp[0][n];
    if (cpn[1] == cpn[n]) {
        cout << dp[0][n] <<"\n";
        return;
    }
    rep (u, 1, n) {
//        cout << dd[u] <<" asdasdasd\n";
        if (dd[u]) {
            res = max(res, spt2[u][0]);
//            cout << u <<" "<<spt2[u][0] <<"\n";
        }
    }
    cout << res <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +33
2 1
0 1
*/

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