Submission #1212052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212052		loom	Train (APIO24_train)	C++20	5 / 100	1018 ms	77684 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)5e18
#define nl '\n'

ll solve(int n, int m, int w, vector<int> p, vector<int> x, vector<int> y, vector<int> a, vector<int> b, vector<int> c, vector<int> l, vector<int> r){
	map<pair<ll,ll>, vector<tuple<ll,ll,ll>>> g;
   vector<ll> adj[n];
   for(ll i=0; i<m; i++){
      g[{x[i], a[i]}].push_back({y[i], b[i], c[i]});
      adj[x[i]].push_back(a[i]);
      adj[y[i]].push_back(b[i]);
   }

   for(ll i=0; i<n; i++){
      auto &v = adj[i];
      sort(v.begin(), v.end());

      for(ll j=1; j<v.size(); j++){
         g[{i, v[j-1]}].push_back({i, v[j], 0});
      }
   }

   if(adj[0].empty()) return -1;
   g[{0, 0}].push_back({0, adj[0][0], 0});

   l.push_back(-1);
   r.push_back(-1);
   sort(l.begin(), l.end());
   sort(r.begin(), r.end());

   #define tup tuple<ll,ll,ll, ll>
   priority_queue<tup, vector<tup>, greater<tup>> pq;
   map<tuple<ll,ll,ll>, ll> dist;
   pq.push({0, 0, 0, 0});
   dist[{0, 0, 0}] = 0;

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

      auto it = upper_bound(l.begin(), l.end(), t);
      ll il = it - l.begin();
      ll rt = (tf ? r[il-1] : -1);

      for(auto [ch, tt, ww] : g[{v, t}]){
         ll ir = -1;
         it = --lower_bound(r.begin(), r.end(), tt);
         if(*it < tt) ir = it - r.begin();
         else if(it != r.begin()) ir = prev(it) - r.begin(); 

         ll td = d;
         if(v == ch) td += max(0ll, ir-il+1) * p[v];
         
         if((!tf or rt < tt) and (!dist.count({ch, tt, 0}) or td + ww < dist[{ch, tt, 0}])){
            dist[{ch, tt, 0}] = td + ww;
            pq.push({td + ww, ch, tt, 0});
         }
         
         if(v == ch and rt < tt) td += p[v];
         if(!dist.count({ch, tt, 1}) or td + ww < dist[{ch, tt, 1}]){
            dist[{ch, tt, 1}] = td + ww;
            pq.push({td + ww, ch, tt, 1});
         } 
      }
   }

   ll ans = inf;
   for(ll t : adj[n-1]){
      ll ix = upper_bound(l.begin(), l.end(), t) - l.begin();
      ll td = (w+1 - ix) * p[n-1];
      
      ll il = l[ix-1];
      ll ir = r[ix-1];
      
      if(dist.count({n-1, t, 0})) ans = min(ans, dist[{n-1, t, 0}] + td + (ir > t ? p[n-1] : 0));
      if(dist.count({n-1, t, 1})) ans = min(ans, dist[{n-1, t, 1}] + td);
   }

   return ans == inf ? -1 : ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60