Submission #518904

#	Time	Username	Problem	Language	Result	Execution time	Memory
518904		azberjibiou	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	358 ms	34608 KiB

commuter_pass

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100020;
const int mxM=2500000;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1000000000000000001;
int N, M, S, T, U, V;
vector <pll> v[mxN];
ll dis[4][mxN];
priority_queue <pll> pq;
bool Chk[mxN];
vector <int> rv[2][mxN];
int rdeg[mxN];
queue <int> que;
ll sub[2][mxN];
ll ans=INF;
void dijkstra(int st, int idx)
{
    while(!pq.empty())  pq.pop();
    for(int i=1;i<=N;i++)   Chk[i]=false;
    for(int i=1;i<=N;i++)   dis[idx][i]=INF;
    dis[idx][st]=0;
    pq.push({0, st});
    while(!pq.empty())
    {
        int now=pq.top().sec;
        pq.pop();
        if(Chk[now])    continue;
        Chk[now]=true;
        for(pll nxt : v[now])
        {
            if(dis[idx][nxt.fir]>dis[idx][now]+nxt.sec)
            {
                dis[idx][nxt.fir]=dis[idx][now]+nxt.sec;
                pq.push({-dis[idx][nxt.fir], nxt.fir});
            }
        }
    }
}
void dfs0(int now)
{
    Chk[now]=true;
    for(pll nxt : v[now])   if(dis[0][now]+dis[1][nxt.fir]+nxt.sec==dis[0][T])
    {
        rv[0][now].push_back(nxt.fir);
        rv[1][nxt.fir].push_back(now);
        rdeg[now]++;
        if(!Chk[nxt.fir])   dfs0(nxt.fir);
    }
}
void dfs1(int now)
{
    Chk[now]=true;
    sub[0][now]=dis[3][now];
    sub[1][now]=dis[2][now];
    for(int nxt : rv[0][now])
    {
        if(!Chk[nxt])   dfs1(nxt);
        sub[0][now]=min(sub[0][now], sub[0][nxt]);
        sub[1][now]=min(sub[1][now], sub[1][nxt]);
    }
}
int main()
{
    gibon
    cin >> N >> M >> S >> T >> U >> V;
    for(int i=0;i<M;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].emplace_back(b, c);
        v[b].emplace_back(a, c);
    }
    dijkstra(S, 0);
    dijkstra(T, 1);
    dijkstra(U, 2);
    dijkstra(V, 3);
    /*for(int i=0;i<4;i++)
    {
        for(int j=1;j<=N;j++)
        {
            printf("dis[%d][%d]=%lld\n", i, j, dis[i][j]);
        }
    }*/
    for(int i=1;i<=N;i++)   Chk[i]=false;
    dfs0(S);
    for(int i=1;i<=N;i++)   if(Chk[i] && !rdeg[i])  que.push(i);
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        if(now==T)  continue;
        Chk[now]=false;
        for(int nxt : rv[1][now])
        {
            rdeg[nxt]--;
            if(!rdeg[nxt])  que.push(nxt);
        }
    }
    vector <int> tmp;
    for(int i=1;i<=N;i++)
    {
        if(!Chk[i])
        {
            rv[0][i].clear();   rv[1][i].clear();
            continue;
        }
        tmp.clear();
        for(int ele : rv[0][i]) if(Chk[ele])    tmp.push_back(ele);
        swap(tmp, rv[0][i]);
        tmp.clear();
        for(int ele : rv[1][i]) if(Chk[ele])    tmp.push_back(ele);
        swap(tmp, rv[1][i]);
    }
    for(int i=1;i<=N;i++)   Chk[i]=false;
    dfs1(S);
    for(int i=1;i<=N;i++)   if(Chk[i])
    {
        ans=min(ans, dis[2][i]+sub[0][i]);
        ans=min(ans, dis[3][i]+sub[1][i]);
    }
    ans=min(ans, dis[2][V]);
    cout << ans;
}

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