Submission #459641

#TimeUsernameProblemLanguageResultExecution timeMemory
459641nickmet2004Aesthetic (NOI20_aesthetic)C++11
0 / 100
684 ms71720 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 300005; ll n , m , au[300005] , av[300005] , aw[300005]; ll u , v , w , A; vector<pair<ll, pair<ll , ll> > > adj[300005]; ll d1[300005] , dn[300005] , f[300005] , par[300005] , path[300005] , son[300005]; multiset<pair<ll , ll>> S; vector<ll> B[300005] , T[300005]; void q(ll x){ f[x] = 1; for(auto y : adj[x]){ //cout << "h"; auto it = S.find({dn[y.first] + y.second.first + d1[x] , y.second.second}); if(f[y.first]) S.erase(it); else S.insert({dn[x] + y.second.first + d1[y.first] , y.second.second}); } } void dfs(int u , int p){ if(path[u]) son[u] = u; else son[u] = son[p]; T[son[u]].emplace_back(u); for(int v : B[u]) dfs(v , u); } main (){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i =0; i <m; ++i) cin >> au[i] >> av[i] >> aw[i]; for(int i = m - 1; ~i; --i){ u = au[i] , v = av[i] , w= aw[i]; adj[u].push_back({v , {w , A}}); adj[v].push_back({u , {w , A}}); A = max(A , w); //cout << "j"; } for(int i = 1; i <= n; ++i) d1[i] = dn[i] = 1e18; d1[1] = 0; dn[n] = 0; priority_queue<pair<ll , ll> > pq; pq.push({0 , 1}); while(pq.size()){ auto T = pq.top(); pq.pop(); u = T.second , w = -T.first; if(f[u])continue; f[u] = 1; for(auto e : adj[u]){ v = e.first; if(!f[v] && d1[v] > w + e.second.first){ par[v] = u; d1[v] = w + e.second.first; pq.push({-d1[v] , v}); } } //cout << "k"; } for(int i = 1; i <= n; ++i)f[i] = 0; //memset(f , 0 ,sizeof(f)); pq.push({0, n}); while(pq.size()){ auto T = pq.top(); pq.pop(); u = T.second , w = -T.first; if(f[u])continue; f[u] = 1; for(auto e : adj[u]){ v = e.first; if(!f[v] && dn[v] > w + e.second.first){ dn[v]= w + e.second.first; pq.push({-dn[v] , v}); } } //cout << "l"; } ll X = n; while(1){ path[X] = 1; if(X == 1) break; X = par[X]; //cout << "n"; } for(int i = 1; i <= n; ++i)B[par[i]].emplace_back(i); dfs(1 , 0); for(int i = 1; i <= n; ++i) f[i] =0; ll s = n; ll ans = d1[n]; //cout << "ka"; ll k; while(1){ //cout << "ha"; if(s == 1)break; for(ll v : T[s]) q(v); s = par[s]; k = S.begin()->first + S.begin()->second; auto i = S.begin(); ++i; if(i != S.end()) k =min(k , i->first); ans = max(ans , k); } cout << ans; raise(1); }

Compilation message (stderr)

Aesthetic.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main (){
      | ^~~~
#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...