Submission #1202363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202363		zeta7532	Train (APIO24_train)	C++20	5 / 100	138 ms	26256 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

#include <vector>

using PP = pair<ll,ll>;
const ll INF = 1LL<<60;

long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R) {
    vector<pair<ll,ll>> P;
    P.push_back({0,0});
    rep(i,M){
        P.push_back({X[i],A[i]});
        P.push_back({Y[i],B[i]});
    }                
    sort(all(P));
    P.erase(unique(all(P)),P.end());
    ll K=P.size();
    vector<vector<pair<ll,ll>>> G(K);
    rep(i,K){
        if(i<K-1){
            if(P[i].fi==P[i+1].fi){
                G[i].push_back({i+1,0});
            }
        }
    }
    rep(i,M){
        ll a=lower_bound(all(P),pair<ll,ll>(X[i],A[i]))-P.begin();
        ll b=lower_bound(all(P),pair<ll,ll>(Y[i],B[i]))-P.begin();
        G[a].push_back({b,C[i]});
    }
    vector<ll> dis(K,INF);                
    priority_queue<PP,vector<PP>,greater<PP>> pq;
    dis[0]=0;
    pq.emplace(dis[0],0);
    while(!pq.empty()){
        PP p=pq.top();
        pq.pop();
        ll v=p.se;
        if(p.fi>dis[v]) continue;
        for(auto e:G[v]){
            if(dis[e.fi]>dis[v]+e.se){
                dis[e.fi]=dis[v]+e.se;
                pq.emplace(dis[e.fi],e.fi);
            }
        }
    }
    ll ans=INF;
    rep(i,K){
        if(P[i].fi==N-1){
            ans=min(ans,dis[i]);
        }
    }      
    if(ans==INF) ans=-1;     
	return ans;
}

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