Submission #705834

#TimeUsernameProblemLanguageResultExecution timeMemory
705834noeditAesthetic (NOI20_aesthetic)C++17
38 / 100
613 ms48564 KiB
#include <bits/stdc++.h> //#include <quadmath.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#define sz(x) (int)x.size() //#define sqr(x) x*x //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native") //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("no-stack-protector") //#pragma GCC optimize("fast-math") using namespace std; //using namespace __gnu_pbds; #define int long long //#define ld long double //template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; const int INF = 1e18; vector<vector<pair<int, int> > > g; vector<int> es; vector<int> tin, go; vector<ll> suff; vector<bool> used; vector<ll> d1, dn; int timer = 0; bool flag = 0; void dfs(int v, int p, ll x) { used[v] = 1; tin[v] = go[v] = timer++; for (auto&[u, ind] : g[v]) { if (p == u) continue; if (min(d1[v] + dn[u], d1[u] + dn[v]) + es[ind] >= x) continue; if (used[u]) { go[v] = min(go[v], tin[u]); } else { dfs(u, v, x); go[v] = min(go[v], go[u]); if (go[u] > tin[v] && min(d1[v] + dn[u], d1[u] + dn[v]) + es[ind] + suff[ind + 1] >= x) { flag = 1; } } } } bool f(ll x) { flag = 0; timer = 0; fill(tin.begin(), tin.end(), 0); fill(go.begin(), go.end(), INF); fill(used.begin(), used.end(), 0); dfs(0, -1, x); return flag; } void dijkstra(int s, vector<ll>& dist) { fill(dist.begin(), dist.end(), 1e18); set<pair<ll, int> > st; st.insert({0, s}); dist[s] = 0; while (!st.empty()) { auto [d, v] = *st.begin(); st.erase(st.begin()); for (auto&[u, ind] : g[v]) { ll w = es[ind]; if (dist[u] > dist[v] + w) { st.erase({dist[u], u}); dist[u] = dist[v] + w; st.insert({dist[u], u}); } } } } void solve() { int n, m; cin >> n >> m; es.resize(m); suff.resize(m + 1); g.resize(n); tin.resize(n); d1.resize(n); dn.resize(n); go.resize(n); used.resize(n); for (int i = 0; i < m; i++) { int x, y, z; cin >> x >> y >> z; x--; y--; g[x].push_back({y, i}); g[y].push_back({x, i}); es[i] = z; } suff[m - 1] = es[m - 1]; for (int i = m - 2; i >= 0; i--) { suff[i] = max(suff[i + 1], es[i]); } dijkstra(0, d1); dijkstra(n - 1, dn); ll lt = d1[n - 1], rt = d1[n - 1] + suff[0] + 1; while (rt - lt > 1) { ll mid = (lt + rt) >> 1; if (f(mid)) { lt = mid; } else { rt = mid; } } cout << lt; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; t = 1; while (t--) { solve(); } return 0; } /* 4 4 1 2 1 3 1 1 1 2 1 3 1 4 */
#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...