Submission #892665

#TimeUsernameProblemLanguageResultExecution timeMemory
892665CDuongAesthetic (NOI20_aesthetic)C++17
0 / 100
1987 ms49748 KiB
/* #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 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; void reset_check() { res_check = -1; for (int i = 1; i <= n; ++i) { G[i].clear(); vis[i] = false; } } int low[mxN], tin[mxN], tdfs; void dfs(int v, int p) { vis[v] = true; 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]) { res_check = max(res_check, min(dis1[u] + disn[v], dis1[v] + disn[u]) + w[ei] + max_w[ei]); } } } } 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) { G[u].emplace_back(v, i); G[v].emplace_back(u, i); } } dfs(1, 0); 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 = n - 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 }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...