Submission #1210780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210780		thenightguy	Aesthetic (NOI20_aesthetic)	C++20	0 / 100	2097 ms	60964 KiB

Aesthetic

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 2e9
#define nl '\n'

const int N = 3e5+1;
vector<tuple<int,int,int>> g[N];
int n;

vector<int> Dijkstra(int s){
   priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
   vector<int> dist(n+1, inf);
   pq.push({0, s});
   dist[s] = 0;

   while(!pq.empty()){
      auto [d, v] = pq.top();
      pq.pop();
      if(dist[v] != d) continue;

      for(auto [ch, w, i] : g[v]){
         if(d + w < dist[ch]){
            dist[ch] = d + w;
            pq.push({dist[ch], ch});
         }
      }
   }

   return dist;
}

int vis[N], tin[N], low[N], tf[N], brg[N];
int cnt;

int dfs(int v, int p){
   vis[v] = 1;
   tin[v] = low[v] = cnt++;

   int ft = (v == n);
   for(auto [ch, w, i] : g[v]){
      if(!tf[i] or ch == p) continue;
      if(vis[ch]){
         low[v] = min(low[v], tin[ch]);
         continue;
      }

      int res = dfs(ch, v);
      ft |= res;
      low[v] = min(low[v], low[ch]);

      if(res and tin[v] < low[ch]) brg[i] = 1;
   }

   return ft;
}

inline void solve(){
   int m;
   cin>>n>>m;

   vector<tuple<int,int,int>> e;
   for(int i=0; i<m; i++){
      int a, b, w;
      cin>>a>>b>>w;

      g[a].push_back({b, w, i});
      g[b].push_back({a, w, i});
      e.push_back({a, b, w});
   }

   int p[m], mx = 0;
   for(int i=m-1; i>=0; i--){
      auto [a, b, w] = e[i];
      p[i] = mx;
      mx = max(mx, w);
   }

   auto d1 = Dijkstra(1);
   auto dn = Dijkstra(n);

   int lo = d1[n], hi = 1e15;
   while(lo < hi){
      int md = (lo+hi+1)/2;

      for(int i=0; i<m; i++){
         auto [a, b, w] = e[i];
         tf[i] = (min(d1[a] + dn[b], d1[b] + dn[a]) + w < md);
      }

      fill(vis, vis+n+1, 0);
      fill(brg, brg+m+1, 0);
      cnt = 0;
      dfs(1, 0);

      int pos = !vis[n];
      for(int i=0; i<m; i++){
         auto [a, b, w] = e[i];
         if(brg[i] and min(d1[a] + dn[b], d1[b] + dn[a]) + w + p[i] >= md) pos = 1;
      }

      if(pos) lo = md;
      else hi = md-1;
   }

   cout<<lo;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27