Submission #329485

#TimeUsernameProblemLanguageResultExecution timeMemory
329485KuuhakuAesthetic (NOI20_aesthetic)C++17
100 / 100
723 ms49900 KiB
//Nov21-2020 #define tasknames "aesthetic" #include <iostream> #include <stdio.h> #include <vector> #include <queue> #include <stack> using namespace std; const int maxn=3e5+2; int n, m, x[maxn], y[maxn], c[maxn], maxc[maxn], Time=0, num[maxn], low[maxn]; long long d[2][maxn]; bool ch[2][maxn], kt; stack<int> st; struct T { int v, w, id; }; vector<T> a[maxn]; void Dijkstra(int s,int h) { priority_queue<pair<long long,int>> pq; for(int i=1;i<=n;i++) d[h][i]=1e18; d[h][s]=0; pq.push({0,s}); while(!pq.empty()) { auto u=pq.top(); pq.pop(); u.first=-u.first; if(u.first!=d[h][u.second]) continue; for(T v:a[u.second]) if(d[h][v.v]>u.first+v.w) { d[h][v.v]=u.first+v.w; pq.push({-d[h][v.v],v.v}); } } } void Enter() { cin>>n>>m; for(int i=1;i<=m;i++) { int u, v, w; cin>>u>>v>>w; a[u].push_back({v,w,i}); a[v].push_back({u,w,i}); x[i]=u;y[i]=v;c[i]=w; } for(int i=m;i>0;i--) maxc[i]=max(maxc[i+1],c[i+1]); Dijkstra(1,0); Dijkstra(n,1); } void Tarjan(int u,int par) { num[u]=low[u]=++Time; for(T v:a[u]) { if(!ch[0][v.id])continue; if(num[v.v]) { if(v.v!=par) low[u]=min(low[u],num[v.v]); } else { Tarjan(v.v,u); if(low[v.v]>num[u]&&num[n]>=num[v.v]&&ch[1][v.id]) kt=true; else low[u]=min(low[u],low[v.v]); } } } bool Check(long long mid) { for(int i=1;i<=m;i++) { long long dist=min(d[0][x[i]]+d[1][y[i]],d[1][x[i]]+d[0][y[i]])+c[i]; ch[0][i]=(dist<=mid); ch[1][i]=((dist+maxc[i])>mid); } fill_n(num,n+1,0); fill_n(low,n+1,1e9); Time=0;kt=false; Tarjan(1,0); if(kt||num[n]==0)return true; return false; } void Solve() { long long l=d[0][n], r=d[0][n]+maxc[1], mid; while(l<=r) { mid=(l+r)/2; if(Check(mid)) l=mid+1; else r=mid-1; } cout<<l; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); Enter(); Solve(); }
#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...