Submission #285005

#TimeUsernameProblemLanguageResultExecution timeMemory
2850053zpAesthetic (NOI20_aesthetic)C++14
35 / 100
825 ms81232 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 500009; vector<pair<ll, pair<ll, ll > > > v[N]; vector<ll> T[N]; ll d1[N],dn[N], f[N], g[N],ea[N],eb[N],ec[N], par[N],path[N],wh[N]; multiset<pair<ll,ll> > S; void ad(ll x){ g[x] = 1; for(auto E : v[x]){ ll y = E.first, l = E.second.first, u= E.second.second; auto it= S.find({dn[y] + l + d1[x], u}); if(g[y] == 1 && it != S.end()) S.erase(it); if(g[y] == 0) S.insert({dn[x] + l + d1[y], u}); } } ll A = 0; main(){ ios_base::sync_with_stdio(false); cin.tie(0); ll n, m; cin >> n >> m; for(ll i = 0; i < m; i++){ cin>>ea[i]>>eb[i]>>ec[i]; } for(ll i = m-1; i >= 0; i--){ ll a = ea[i], b = eb[i], c = ec[i]; if(a == b)cout<<1/0; v[a].push_back({b, {c,A}}); v[b].push_back({a, {c,A}}); A = max(A, c); } for(ll i = 1; i <= n; i++){ d1[i] = 1e18; dn[i] = 1e18; } d1[1] = 0; dn[n] = 0; priority_queue<pair<ll, ll> > q; q.push({0, 1}); while(q.size()){ ll x = q.top().second; q.pop(); if(f[x]) continue; f[x] = 1; for(auto E: v[x]){ ll y = E.first, l = E.second.first; if(!f[y] && d1[y] > d1[x] + l){ d1[y] = d1[x] + l; par[y] = x; q.push({-d1[y], y}); } } } q.push({0, n}); for(ll i = 1; i <= n; i++) f[i] = 0; while(q.size()){ ll x = q.top().second; q.pop(); if(f[x]) continue; f[x] = 1; for(auto E: v[x]){ ll y = E.first, l = E.second.first; if(!f[y] && dn[y] > dn[x] + l){ dn[y] = dn[x] + l; q.push({-dn[y], y}); } } } vector<pair<ll,ll> > W; ll ans = d1[n]; ll X = n; while(1){ path[X] = 1; if(X == 1) break; X = par[X]; } for(ll i = 1; i <= n; i++){ W.push_back({d1[i], i}); } sort(W.begin(), W.end()); for(ll i = 0; i < W.size(); i++){ ll x = W[i].second; if(path[x]) wh[x] = x; else wh[x] = wh[par[x]]; T[wh[x]].push_back(x); } ll x = n; while(1){ for(ll y : T[x]) ad(y); if(x == 1) break; x = par[x]; if(S.size() == 0) continue; ll U = S.begin()->first + S.begin()->second; auto it = S.begin(); it++; if(it != S.end()) U = min(U, it->first); ans = max(ans, U); } cout<<ans<<endl; }

Compilation message (stderr)

Aesthetic.cpp:19:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main(){
      |      ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:29:26: warning: division by zero [-Wdiv-by-zero]
   29 |         if(a == b)cout<<1/0;
      |                         ~^~
Aesthetic.cpp:86:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(ll i = 0; i < W.size(); i++){
      |                   ~~^~~~~~~~~~
#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...