Submission #1210842

#TimeUsernameProblemLanguageResultExecution timeMemory
1210842loomAesthetic (NOI20_aesthetic)C++20
100 / 100
388 ms65572 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]; tuple<int,int,int> e[N]; int d1[N], dn[N], p[N]; int n; void Dijkstra(int s){ auto &dist = (s == 1 ? d1 : dn); priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; fill(dist, 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}); } } } } 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; 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 mx = 0; for(int i=m-1; i>=0; i--){ auto [a, b, w] = e[i]; p[i] = mx; mx = max(mx, w); } Dijkstra(1); Dijkstra(n); int lo = d1[n], hi = d1[n] + p[0]; 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...