Submission #459648

#TimeUsernameProblemLanguageResultExecution timeMemory
459648nickmet2004Aesthetic (NOI20_aesthetic)C++11
73 / 100
880 ms134528 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; ll n , m ,A, au[300002] , av[300002] , aw[300002]; vector<pair<ll, pair<ll , ll> > > adj[300002]; ll d1[300002] , dn[300002] , f[300002] , par[300002] , path[300002] , son[300002]; multiset<pair<ll , ll>> S; vector<ll> B[300002] , T[300002]; void q(ll x){ f[x] = 1; for(auto j : adj[x]){ //cout << "h"; ll y = j.first , l = j.second.first; auto it = S.find({dn[y] + l + d1[x] , j.second.second}); if(f[y]==1) S.erase(it); if(f[y] == 0) S.insert({dn[x] + l + d1[y] , j.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){ ll 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()){ ll u = pq.top().second; pq.pop(); if(f[u])continue; f[u] = 1; for(auto e : adj[u]){ ll v = e.first , l = e.second.first; if(!f[v] && d1[v] > d1[u] + l){ par[v] = u; d1[v] = d1[u] + l; 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()){ ll u = pq.top().second; pq.pop(); if(f[u])continue; f[u] = 1; for(auto e : adj[u]){ ll v = e.first , l = e.second.first; if(!f[v] && dn[v] > dn[u] + l){ dn[v]= dn[u] + l; 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"; while(1){ //cout << "ha"; if(s == 1)break; for(ll v : T[s]) q(v); s = par[s]; ll 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<<endl; }

Compilation message (stderr)

Aesthetic.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | 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...