Submission #1157525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157525		Marco_Escandon	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	33 ms	7468 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
typedef long long ll;
#define x first
#define y second
ll n,m;
vector<vector<pair<ll,ll>>> G,GT,GC1,GC2;
vector<pair<ll,ll>> C;
vector<pair<ll,ll>> A;
vector<ll> CMC1(ll ini)
{
    priority_queue<pair<ll,ll>>q;
    vector<ll> v(n+1,1e16);
    q.push({0,ini});
    ll pl=n;
    if(ini==n) pl=1;
    while(!q.empty())
    {
        pair<ll,ll> node=q.top();q.pop();
        if(v[node.y]==1e16)
        {
            v[node.y]=-node.x;
            if(node.y!=pl)
            for(auto i:G[node.y])
                if(v[i.x]==1e16)
                    q.push({node.x-C[i.y].x,i.x});
        }
    }
    return v;
}
vector<ll> CMC2(ll ini)
{
    priority_queue<pair<ll,ll>>q;
    q.push({0,ini});
    vector<ll> v(n+1,1e16);  
    ll pl=n;
    if(ini==n) pl=1;
    while(!q.empty())
    {
        pair<ll,ll> node=q.top();q.pop();
        if(v[node.y]==1e16)
        {
            v[node.y]=-node.x;
            if(node.y!=pl)
            for(auto i:GT[node.y])
                if(v[i.x]==1e16)
                    q.push({node.x-C[i.y].x,i.x});
        }
    }
    return v;
}
vector<ll>ord1,ord2;
vector<ll>B1,B2;
ll cnt1=1,cnt2=1;
void P1(ll node, ll P)
{
    if(ord1[node]!=0) return;
    ll ordent=cnt1;
    ord1[node]=cnt1++;
    for(auto i:GC1[node])
    {
        if(i.x==P) continue;
        P1(i.x,node);
        if(ord1[i.x]>ord1[node]) B1[i.y]=1;
        ordent=min(ordent,ord1[i.x]);
    }
    ord1[node]=ordent;
}
void P2(ll node, ll P)
{
    if(ord2[node]!=0) return;
    ll ordent=cnt2;
    ord2[node]=cnt2++;
    for(auto i:GC2[node])
    {
        if(i.x==P) continue;
        P2(i.x,node);
        if(ord2[i.x]>ord2[node]) B2[i.y]=1;
        ordent=min(ordent,ord2[i.x]);
    }
    ord2[node]=ordent;
}
ll CMC3(ll ini, ll fin, ll e)
{
    priority_queue<pair<ll,ll>>q;
    vector<ll> v(n+1,1e16);
    q.push({0,ini});
    while(!q.empty())
    {
        pair<ll,ll> node=q.top();q.pop();
        if(node.y==fin) return -node.x;
        if(v[node.y]==1e16)
        {
            v[node.y]=-node.x;
            for(auto i:G[node.y])
                if(v[i.x]==1e16&&i.y!=e)
                    q.push({node.x-C[i.y].x,i.x});
        }
    }
    return 1e16;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    A.resize(m);
    C.resize(m);
    G.resize(n+1);
    GT.resize(n+1);
    for(int i=0; i<m; i++)
    {
        ll a,b;
        cin>>a>>b>>C[i].x>>C[i].y;
        G[a].push_back({b,i});
        GT[b].push_back({a,i});
        A[i]={a,b};
    }
    GC1.resize(n+1);
    GC2.resize(n+1);
    vector<ll> D1=CMC1(1),DT1=CMC2(1);
    vector<ll> DN=CMC1(n),DTN=CMC2(n);
    for(int i=0; i<m; i++)
    {
        if(D1[A[i].x]+DTN[A[i].y]+C[i].x==D1[n]&&D1[n]!=1e16) GC1[A[i].x].push_back({A[i].y,i});
        if(DN[A[i].x]+DT1[A[i].y]+C[i].x==DN[1]&&DN[1]!=1e16) GC2[A[i].x].push_back({A[i].y,i});
    }
    ord1.assign(n+1,0);
    ord2.assign(n+1,0);
    B1.assign(m+1,0);
    B2.assign(m+1,0);
    P1(1,0);
    P2(n,0);
    ll bs=D1[n]+DN[1];
    /*for(int i=1; i<=n; i++)
        cerr<<D1[i]<<" ";
    cerr<<"\n";
    for(int i=1; i<=n; i++)
        cerr<<DN[i]<<" ";
    cerr<<"\n";
    for(int i=1; i<=n; i++)
        cerr<<DT1[i]<<" ";
    cerr<<"\n";
    for(int i=1; i<=n; i++)
        cerr<<DTN[i]<<" ";
    cerr<<"\n";
    for(int i=0; i<m; i++)
        cerr<<B1[i]<<" ";
    cerr<<"\n";
    for(int i=0; i<m; i++)
        cerr<<B2[i]<<" ";
    cerr<<"\n";*/
    for(int i=0; i<m; i++)
    {
        if(B1[i]==0)
            bs=min(bs,(D1[n]+DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y));
        else
        {
            bs=min(bs,(CMC3(1,n,i)+DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y));
        }
        if(B2[i]==0)
            bs=min(bs,(DN[1]+D1[A[i].y]+DTN[A[i].x]+C[i].x+C[i].y));
        else
        {
            bs=min(bs,(CMC3(n,1,i)+D1[A[i].y]+DTN[A[i].x]+C[i].x+C[i].y));
        }    
    }
    if(bs>1e15)
    {
        cout<<-1;
        return 0;
    }
    cout<<bs;
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63