Submission #1167941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167941		ricardsjansons	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	192 ms	19616 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define remin(a,b...) a=min({a,b})
#define remax(a,b...) a=max({a,b})
#define ll long long
#define ld long double
#define pii array<int,2>
#define pll array<ll,2>
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vii vector<array<int,2>>
#define vll vector<array<ll,2>>
#define v2d(T) vector<vector<T>>
#define v3d(T) vector<vector<vector<T>>>
#define pub push_back
#define tup make_tuple
using namespace std;

const ll C=1e9;
const ll M=2e5;

ll n,m,s,t,u,v;
vector<vll> adj;

vl dij(int x){
    vl d(n+1,C*M);
    vb vis(n+1);
    d[x]=0;
    priority_queue<pll>pq;
    pq.push({0,x});
    while(!pq.empty()){
        int i=pq.top()[1];
        pq.pop();
        if(vis[i]){
            continue;
        }
        vis[i]=1;
        for(auto[j,c]:adj[i]){
            if(d[i]+c<d[j]){
                d[j]=d[i]+c;
                pq.push({-d[j],j});
            }
        }
    }
    return d;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s>>t>>u>>v;
    adj.resize(n+1);
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].pub({b,c});
        adj[b].pub({a,c});
    }

    vl du=dij(u);
    vl dv=dij(v);
    vl ds=dij(s);
    vl dt=dij(t);
    vb b(n+1);
    for(int i=1;i<=n;i++){
        b[i]=(ds[i]+dt[i]==ds[t]);
    }
    vll dp(n+1,{C*M,C*M});
    dp[s]={du[s],dv[s]};
    priority_queue<pll>pq;
    pq.push({0,s});
    vb vis(n+1);
    ll res=M*C;
    while(!pq.empty()){
        int i=pq.top()[1];
        pq.pop();
        if(vis[i]){
            continue;
        }
        vis[i]=1;
        for(auto[j,c]:adj[i]){
            if(ds[j]>ds[i]&&b[j]){
                pq.push({-ds[j],j});
                remin(dp[j][0],dp[i][0],du[j]);
                remin(dp[j][1],dp[i][1],dv[j]);
                remin(res,dp[j][0]+dv[j],dp[j][1]+du[j]);
            }
        }
    }
    cout<<min(res,du[v]);
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45