Submission #1210779

#TimeUsernameProblemLanguageResultExecution timeMemory
1210779loomAesthetic (NOI20_aesthetic)C++20
35 / 100
2095 ms60436 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define inf 5e18 #define nl '\n' const int N = 3e5+1; vector<tuple<int,int,int>> g[N]; int n; vector<int> Dijkstra(int s){ priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; vector<int> dist(n+1, inf); pq.push({0, s}); dist[s] = 0; while(!pq.empty()){ auto [d, v] = pq.top(); pq.pop(); if(dist[v] != d) continue; for(auto [ch, w, i] : g[v]){ if(d + w < dist[ch]){ dist[ch] = d + w; pq.push({dist[ch], ch}); } } } return dist; } int vis[N], tin[N], low[N], tf[N]; vector<int> brg; int cnt; int dfs(int v, int p){ vis[v] = 1; tin[v] = low[v] = cnt++; int ft = (v == n); for(auto [ch, w, i] : g[v]){ if(!tf[i] or ch == p) continue; if(vis[ch]){ low[v] = min(low[v], tin[ch]); continue; } int res = dfs(ch, v); ft |= res; low[v] = min(low[v], low[ch]); if(res and tin[v] < low[ch]) brg.push_back(i); } return ft; } inline void solve(){ int m; cin>>n>>m; vector<tuple<int,int,int>> e(m); for(int i=0; i<m; i++){ int a, b, w; cin>>a>>b>>w; g[a].push_back({b, w, i}); g[b].push_back({a, w, i}); e[i] = {a, b, w}; } int p[m], mx = 0; for(int i=m-1; i>=0; i--){ auto [a, b, w] = e[i]; p[i] = mx; mx = max(mx, w); } auto d1 = Dijkstra(1); auto dn = Dijkstra(n); int lo = d1[n], hi = 4e14; while(lo < hi){ int md = (lo+hi+1)/2; for(int i=0; i<m; i++){ auto [a, b, w] = e[i]; tf[i] = (min(d1[a] + dn[b], d1[b] + dn[a]) + w < md); } fill(vis, vis+n+1, 0); brg.clear(); cnt = 0; dfs(1, 0); int pos = !vis[n]; for(int i : brg){ auto [a, b, w] = e[i]; pos |= (min(d1[a] + dn[b], d1[b] + dn[a]) + w + p[i] >= md); } if(pos) lo = md; else hi = md-1; } cout<<lo; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) solve(); return 0; }
#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...