Submission #274229

#TimeUsernameProblemLanguageResultExecution timeMemory
274229dooweyAesthetic (NOI20_aesthetic)C++14
100 / 100
1014 ms71476 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = (int)3e5 + 10; int u[N], v[N], w[N]; int p[N]; vector<pii> T[N]; ll dist[2][N]; bool has[N]; int n,m,c; void dijik(int x){ priority_queue<pii,vector<pii>,greater<pii>> gg; int node; for(int i = 1; i <= n; i ++ ){ dist[c][i]=(ll)1e14; has[i]=false; } dist[c][x]=0ll; gg.push(mp(0,x)); while(!gg.empty()){ node = gg.top().se; gg.pop(); if(has[node]) continue; has[node]=true; for(auto x : T[node]){ if(dist[c][node] + w[x.se] < dist[c][x.fi]){ dist[c][x.fi] = dist[c][node] + w[x.se]; gg.push(mp(dist[c][x.fi], x.fi)); } } } c++; } vector<pii> E[N]; int tin[N]; int low[N]; ll attm; int tt; bool bridge[N]; void dfs(int u, int par){ tin[u] = ++tt; low[u] = tin[u]; for(auto x : E[u]){ if(x.fi == par) continue; if(tin[x.fi] != -1){ low[u] = min(low[u], tin[x.fi]); } else{ dfs(x.fi, u); low[u] = min(low[u], low[x.fi]); if(tin[u] < low[x.fi]){ bridge[x.se] = true; } } } } int ids[N]; int id; void dfs1(int u, int par){ ids[u]=id; for(auto x : E[u]){ if(ids[x.fi] != -1) continue; if(bridge[x.se]) continue; dfs1(x.fi, u); } } bool bad; int pid[N]; int ip[N]; bool vis[N]; void dfs2(int u, int par){ vis[u]=true; for(auto x : E[u]){ if(vis[x.fi]) continue; if(bridge[x.se]){ pid[ids[x.fi]] = ids[u]; ip[ids[x.fi]] = x.se; dfs2(x.fi, u); } else{ dfs2(x.fi, u); } } } bool check(ll dis){ attm = dis; tt = 0; for(int i = 0 ; i < m ; i ++ ){ bridge[i]=false; } for(int i = 1; i <= n; i ++ ){ E[i].clear(); vis[i]=false; tin[i] = -1, low[i] = -1; ids[i] = -1; pid[i] = -1; ip[i] = -1; } id = 0; for(int i = 0 ; i < m ; i ++ ){ if(dist[0][u[i]] + w[i] + dist[1][v[i]] <= dis || dist[0][v[i]] + w[i] + dist[1][u[i]] <= dis){ E[u[i]].push_back(mp(v[i], i)); E[v[i]].push_back(mp(u[i], i)); } } dfs(1, 0); if(tin[n] == -1) return false; // we assume it is reachable at this point bad = false; for(int i = 1; i <= n; i ++ ){ if(tin[i] != -1 && ids[i] == -1){ id ++ ; dfs1(i,-1); } } dfs2(1, 0); int node = ids[n]; int ed; while(node != ids[1]){ ed = ip[node]; node = pid[node]; if(dist[0][u[ed]] + dist[1][v[ed]] + w[ed] + p[ed+1] > dis && dist[1][u[ed]] + dist[0][v[ed]] + w[ed] + p[ed+1] > dis) return false; } return true; } int main(){ fastIO; cin >> n >> m; for(int i = 0 ; i < m ; i ++ ){ cin >> u[i] >> v[i] >> w[i]; T[u[i]].push_back(mp(v[i],i)); T[v[i]].push_back(mp(u[i],i)); } dijik(1); dijik(n); for(int i = m-1; i >= 0 ; i -- ){ p[i]=w[i]; p[i]=max(p[i],p[i+1]); } ll li = dist[0][n], ri = li+p[1]; ll mid; while(li < ri){ mid = (li + ri) / 2; if(check(mid)) ri = mid; else li = mid + 1; } cout << li << "\n"; 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...