Submission #1212031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212031		loom	Train (APIO24_train)	C++20	0 / 100	836 ms	64628 KiB

train

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

const ll T = 1001;

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});
      }
   }
   g[{0, 0}].push_back({0, adj[0][0], 0});

   vector<pair<ll,ll>> mls(w);
   for(ll i=0; i<w; i++) mls[i] = {l[i], r[i]};
   sort(mls.begin(), mls.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 = lower_bound(mls.begin(), mls.end(), make_pair(t, inf));
      ll il = it - mls.begin();

      ll rt = -1;
      if(tf and it != mls.begin()) rt = prev(it)->second;

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

         ll td = d;
         if(v == ch) td += max(0ll, ir-il+1) * p[v];
         
         if(dist.count({ch, tt, 0}) == 0 or (!tf or rt < tt) and 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}) == 0 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]){
      auto it = lower_bound(mls.begin(), mls.end(), make_pair(t, inf));
      ll td = (mls.end() - it) * p[n-1];

      ll il, ir = -1;
      if(it != mls.begin()){
         it--;
         il = it->first;
         ir = it->second;
      }
      
      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: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60