Submission #892697

#	Time	Username	Problem	Language	Result	Execution time	Memory
892697		CDuong	Aesthetic (NOI20_aesthetic)	C++17	16 / 100	1903 ms	69460 KiB

Aesthetic

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 3e5 + 5;
const int mxM = 3e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

int n, m;
bool vis[mxN];
vector<pair<int, int>> G[mxN], Gn[mxN];
int w[mxM], max_w[mxM];
i64 dis1[mxN], disn[mxN];
pair<int, int> edges[mxM];

i64 dijkstra() {
    fill(dis1 + 1, dis1 + n + 1, oo);
    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;

    dis1[1] = 0; pq.emplace(0, 1);
    while (not pq.empty()) {
        i64 cdis = pq.top().ff;
        int v = pq.top().ss;
        pq.pop();
        if (cdis != dis1[v]) continue;
        for (auto [u, ei] : G[v]) {
            if (dis1[v] + w[ei] < dis1[u]) {
                dis1[u] = dis1[v] + w[ei];
                pq.emplace(dis1[u], u);
            }
        }
    }

    fill(disn + 1, disn + n + 1, oo);
    disn[n] = 0; pq.emplace(0, n);
    while (not pq.empty()) {
        i64 cdis = pq.top().ff;
        int v = pq.top().ss;
        pq.pop();
        if (cdis != disn[v]) continue;
        for (auto [u, ei] : G[v]) {
            if (disn[v] + w[ei] < disn[u]) {
                disn[u] = disn[v] + w[ei];
                pq.emplace(disn[u], u);
            }
        }
    }

    return dis1[n];
}

i64 res_check;
bool vis_n[mxN];
int low[mxN], tin[mxN], tdfs;

void reset_check() {
    res_check = -1, tdfs = 0;
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
        vis[i] = vis_n[i] = false;
    }
}

void dfs(int v, int p) {
    vis[v] = true, vis_n[v] = (v == n);
    tin[v] = low[v] = ++tdfs;
    for (auto [u, ei] : G[v]) {
        if (u == p) continue;
        if (vis[u]) {
            low[v] = min(low[v], tin[u]);
        }
        else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v] && vis_n[u]) {
                // cout << u << " " << v << " " << ei << " " << w[ei] << " " << max_w[ei] << endl;
                res_check = max(res_check, min(dis1[u] + disn[v], dis1[v] + disn[u]) + w[ei] + max_w[ei]);
            }
            vis_n[v] |= vis[u];
        }
    }
}

bool check(i64 val) {
    reset_check();
    for (int i = 1; i <= m; ++i) {
        int u = edges[i].ff, v = edges[i].ss;
        if (min(dis1[u] + disn[v], dis1[v] + disn[u]) + w[i] <= val) {
            // cout << u << " " << v << endl;
            G[u].emplace_back(v, i);
            G[v].emplace_back(u, i);
        }
    }
    dfs(1, 0);
    // cout << res_check << endl << endl;
    return !(res_check > val);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, cw;
        cin >> u >> v >> cw;
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
        edges[i] = {u, v};
        w[i] = max_w[i - 1] = cw;
    }
    for (int i = m - 1; i >= 1; --i)
        max_w[i] = max(max_w[i], max_w[i + 1]);

    i64 miin = dijkstra();
    i64 l = miin, r = miin + 1e9;
    while (l < r) {
        i64 mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

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