Submission #307292

#	Time	Username	Problem	Language	Result	Execution time	Memory
307292		Spongiforma	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2093 ms	33520 KiB

commuter_pass

#include <bits/stdc++.h>
#define INF LLONG_MAX/2
#define sacnf scanf
#define scnf scanf
#define scnaf scanf
#define CRLF <<'\n';
#define ALL(v) v.begin,v.end()
#define SIZE(v) (int)v.size()
#define PRPAIR(x) x.first << x.second
#define DEBUG(x) do { std::cerr <<(x)<<'\n'; } while (0)
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ii> pip;
typedef vector<ll> vi;
#define N 100005
#define M 200005

int n,m,s,t,u,v;
vi ds,dt,du,dv;
vector<ii> adj[N];

void sssp(int i,vi &dist){
    dist.assign(n,INF);
    dist[i] = 0;
    priority_queue<ii,vector<ii>,greater<ii>> q;
    q.push({0,i});
    while(!q.empty()){
        ii a=q.top(); q.pop();
        ll d = a.first, u = a.second;
        if (dist[u] < d)
            continue;
        for(auto v: adj[u]){
            if (dist[u] + v.second < dist[v.first]){
                dist[v.first] = dist[u] + v.second;
                q.push({dist[v.first],v.first});
            }
        }
    }
}
bitset<N> onsp,vis;

vi g[N],g2[N];

void bs(int i){
    onsp[i] = 1;
    vis[i] = 1;
    if (i == s)
        return;
    for(auto v: adj[i]){
        if (dt[i] + v.second + ds[v.first] == ds[t]){
            g2[i].push_back(v.first);
            g[v.first].push_back(i);
        }
        if (!vis[v.first])
            bs(v.first);
    }
}

ll mem1[N],mem2[N];

ll mutosp1(int i){
    if (mem1[i]!=-1)
        return mem1[i];
    if (i == s){
        mem1[i] = du[s];
        return mem1[i];
    }
    mem1[i] = du[i];
    for(auto v: g2[i]){
        mem1[i] = min(mem1[i],mutosp1(v));
    }
    return mem1[i];
}
ll mutosp2(int i){
    if (mem2[i]!=-1)
        return mem2[i];

    if (i == t){
        mem2[i] = du[t];
        return mem2[i];
    }
    mem2[i] = du[i];
    for(auto v: g[i]){
        mem2[i] = min(mem2[i],mutosp2(v));
    }
    return mem2[i];
}

ll dfs(int i){
    ll minv=dv[i]+mem2[i];
    for(auto v: adj[i]){
        if (ds[i] + v.second + dt[v.first] == ds[t])
            minv = min(dfs(v.first),minv);
    }
    return minv;
}


ll dfs2(int i){
    ll minv=dv[i]+mem1[i];
    for(auto v: adj[i]){
        if (dt[i] + v.second + ds[v.first] == ds[t])
            minv = min(dfs2(v.first),minv);
    }
    return minv;
}

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
    s--,t--,u--,v--;

    rep(i,0,m){
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        a--,b--;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    sssp(s,ds),sssp(t,dt),sssp(u,du),sssp(v,dv);
    vis.reset();
    bs(t);
    memset(mem1,-1,sizeof mem1);
    memset(mem2,-1,sizeof mem2);
    mutosp1(t);
    mutosp2(s);
    ll ans = dfs(s);
    ans = min(ans,dfs2(t));
    ans = min(du[v],ans);
    cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |     scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  116 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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