Submission #293260

#TimeUsernameProblemLanguageResultExecution timeMemory
293260crossing0verAesthetic (NOI20_aesthetic)C++17
0 / 100
6 ms5280 KiB
#include<bits/stdc++.h> #define all(x) (x).begin(),(x).end() #define pii pair<int,int> #define ll long long #define pb push_back #define vi vector<int> #define se second #define fi first using namespace std; const int N = 1e5+5; vector<pii> adj[N]; int n,m; int A[N],B[N],W[N],NUM[N][2],MX[N],par[N],good[N],sub[N],id[N]; ll D[N],FROM_N[N]; set<pii> path; void dijkstra(int s) { priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq; pq.push({0,s}); vector<bool> vis(n+1); vector<ll> d(n+1); for (int i = 1; i <= n; i++) d[i] = 10000000000000000; d[s] = 0; par[s] = 0; id[s] = 0; while(!pq.empty()) { auto i1 = pq.top(); pq.pop(); int v = i1.se; if (vis[v]) continue; ll dis = i1.fi; vis[v] = 1; for (auto i : adj[v]) if (!vis[i.fi] && d[i.fi] > dis + i.se) { d[i.fi] = dis + i.se; id[i.fi] = id[v] + 1; par[i.fi] = v; pq.push({d[i.fi],i.fi}); } } if (s == n) for (int i = 1; i <= n; i++) FROM_N[i] = d[i]; else { for (int i = 2; i <= n; i++) { path.insert({i,par[i]}); path.insert({par[i],i}); } for (int i = 1; i <= n; i++) D[i] = d[i]; int j = n; good[1] = 1; while(j != 1) { good[j] = 1; j = par[j]; } vector<pair<ll,int> > g; for (int i =1 ; i <= n; i++) { g.pb({d[i],i}); } sort(all(g)); for (auto i1 : g) { int v = i1.se; if (!good[v]) sub[v] = sub [ par[v] ]; else sub[v] = v; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < m; i++) { int a,b,w; cin >> a >> b >> w; A[i] = a, B[i] = b; W[i] = w; NUM[i][0] = adj[a].size(); NUM[i][1] = adj[b].size(); adj[a].pb({b,w}); adj[b].pb({a,w}); MX[i] = w; } dijkstra(n); dijkstra(1); // cout << FROM_N[1];exit(0); for (int i = m-2; i >= 0; i--) MX[i] = max(MX[i],MX[i+1]); ll ans = D[n]; // cout << D[n];exit(0); /*for (int i = 0; i < m; i++) { int a = A[i], b = B[i]; adj[a][NUM[i][0]].se += MX[i+1]; adj[b][NUM[i][1]].se += MX[i+1]; // dijkstra priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq; pq.push({0,1}); vector<bool> vis(n+1); vector<ll> d(n+1); for (int i = 1; i <= n; i++) d[i] = 10000000000000000; d[1] = 0; while(!pq.empty()) { auto i1 = pq.top(); pq.pop(); int v = i1.se; if (vis[v]) continue; ll dis = i1.fi; if (v == n) { ans = max(ans,dis); break; } vis[v] = 1; for (auto i : adj[v]) if (!vis[i.fi] && d[i.fi] > dis + i.se) { d[i.fi] = dis + i.se; pq.push({d[i.fi],i.fi}); } } // replace adj[a][NUM[i][0]].se -= MX[i+1]; adj[b][NUM[i][1]].se -= MX[i+1]; }*/ for (int i = 0; i < m; i++) { int a = A[i], b = B[i]; if (path.count({a,b}) == 0) continue; if (id[a] > id[b]) swap(a,b); ll C = D[n]; C += MX[i+1]; //adj[a][NUM[i][0]].se += MX[i+1]; //adj[b][NUM[i][1]].se += MX[i+1]; // dijkstra for (int i = 0; i < m; i++) { int x = A[i], y = B[i]; if (id[sub[x]] > id[sub[y]]) swap(x,y); if (x == a && y == b ) continue; if (id[sub[x]] > id[a] || id[sub[y]] < id[b]) continue; C = min(C,D[x] + FROM_N[y] + W[i]); } ans = max(ans,C); } // replace //adj[a][NUM[i][0]].se -= MX[i+1]; //adj[b][NUM[i][1]].se -= MX[i+1]; cout << ans; }
#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...