Submission #653221

#	Time	Username	Problem	Language	Result	Execution time	Memory
653221		ash_gamertable	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1650 ms	37368 KiB

commuter_pass

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fastio          ios_base::sync_with_stdio(0); cin.tie(0);


// g->{i,j} i is the node and j is the wt

vector<vector<pii>> make_dag(vi &ds,vi &dv,int src,int dest,vector<vector<pii>> &g,int n)
{
    vector<vector<pii>> dag(n+1);
    for(int i=1;i<=n;i++)
    {
        for(auto x:g[i]) if(ds[i]+x.ss+dv[x.ff]==ds[dest]) dag[i].pb({x.ff,x.ss});
    }
    return dag;
}


void djkstra(int src,vi &dist,vector<vector<pii>> &g)
{
    priority_queue<vi,vector<vi>,greater<vi>> pq;
    pq.push({0,src,-1,0});
    while(!pq.empty()){
        vi temp=pq.top();pq.pop();
        int node=temp[1],till=temp[0],p=temp[2],wt=temp[3];
        if(dist[node]==inf || dist[node]==till){
            // if(p!=-1) dag[p].pb({node,wt});
            if(dist[node]==inf)
            for(auto x:g[node]) pq.push({till+x.ss,x.ff,node,x.ss});
            dist[node]=till;
        }
    }
}
vi topo(vector<vector<pii>> &g,int n,vi &vis)
{
    vi inorder(n+1,0),topo;
    queue<int> q;
    for(int i=1;i<=n;i++) for(auto x:g[i]) inorder[x.ff]++;
    for(int i=1;i<=n;i++) if(inorder[i]==0 && vis[i]==1) q.push(i);
    while(!q.empty()){
        int t=q.front();q.pop();
        topo.pb(t);
        for(auto node:g[t]){
            inorder[node.ff]--;
            if(inorder[node.ff]==0 && vis[node.ff]==1) q.push(node.ff);
        }
    }
    return topo;
}
int s1(vector<vector<pii>> &inv_g,vi &topo,vi &du,vi &dv,int n)
{
    int ans=inf;
    vi dp(n+1,inf);
    for(int i=0;i<topo.size();i++){
        int mn=inf;
        for(auto x:inv_g[topo[i]]) 
        {
            ans=min(ans,du[x.ff]+dp[x.ff]);
            mn=min(mn,dp[x.ff]);
        }
        dp[topo[i]]=min(mn,dv[topo[i]]);
    }
    return ans;
}

int dfs(int node,vi &du,vector<vector<pii>> &dag,vi &dp)
{
    if(dp[node]!=-1) return dp[node];
    int ans=inf;
    for(auto x:dag[node]) ans=min(ans,dfs(x.ff,du,dag,dp));
     return (dp[node]=min(ans,du[node])); 
}


int solve(vector<vector<pii>> &dag,int u,int v,vi &du,vi &dv,int n,int s)
{
    int ans=du[v];
    // vi tp=topo(dag,n);
    // vector<vector<pii>> inv_g(n+1);
    // for(int i=1;i<=n;i++){
    //     for(auto x:dag[i]) inv_g[x.ff].pb({i,x.ss});
    // }
    vi dp(n+1,-1);
    dfs(s,dv,dag,dp);    
    for(int i=1;i<=n;i++)
    if(dag[i].size()>0 && dp[i]!=-1) 
    ans=min(ans,du[i]+dp[i]);
    return ans;
}

int32_t main()
{
    fastio;
    int n,m,s,t,u,v,x,y,wt;
    cin>>n>>m>>s>>t>>u>>v;
    vector<vector<pii>> g(n+1),dag_s;
    for(int i=0;i<m;i++){
        cin>>x>>y>>wt;
        g[x].pb({y,wt});
        g[y].pb({x,wt});
    }
    vi ds(n+1,inf),du(n+1,inf),dv(n+1,inf),dt(n+1,inf);
    djkstra(s,ds,g);
    djkstra(u,du,g);
    djkstra(v,dv,g);
    djkstra(t,dt,g);

    dag_s=make_dag(ds,dt,s,t,g,n);
    // for(int i=1;i<=n;i++){
    //     for(auto x:dag_s[i]) cout<<i<<"*"<<x.ff<<" "<<x.ss<<endl;
    // }
    // for(int i=1;i<=n;i++) cout<<dv[i]<<" ";
    vi vis(n+1,0);
    vector<vector<pii>> inv_g(n+1);
    for(int i=1;i<=n;i++){
        for(auto x:dag_s[i]) 
        {
            inv_g[x.ff].pb({i,x.ss});
            vis[i]=1;vis[x.ff]=1;
        }
    }
    vi tp=topo(dag_s,n,vis);





    int ans=du[v];
    ans=min(ans,solve(dag_s,u,v,du,dv,n,s));
    ans=min(ans,solve(dag_s,v,u,dv,du,n,s));
    ans=min(ans,s1(inv_g,tp,du,dv,n));
    ans=min(ans,s1(inv_g,tp,dv,du,n));

    cout<<ans<<"\n";



return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void djkstra(long long int, std::vector<long long int>&, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
commuter_pass.cpp:46:39: warning: unused variable 'p' [-Wunused-variable]
   46 |         int node=temp[1],till=temp[0],p=temp[2],wt=temp[3];
      |                                       ^
commuter_pass.cpp:46:49: warning: unused variable 'wt' [-Wunused-variable]
   46 |         int node=temp[1],till=temp[0],p=temp[2],wt=temp[3];
      |                                                 ^~
commuter_pass.cpp: In function 'long long int s1(std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&, long long int)':
commuter_pass.cpp:75:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<topo.size();i++){
      |                 ~^~~~~~~~~~~~

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