Submission #1157580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157580		Marco_Escandon	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	900 ms	3988 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
typedef long long ll;
#define x first
#define y second
int n,m;
vector<vector<pair<int,int>>> G,GT,GC1,GC2;
vector<pair<int,int>> C;
vector<pair<int,int>> A;
vector<ll> CMC1(int ini)
{
    priority_queue<pair<ll,int>>q;
    vector<ll> v(n+1,1e16);
    q.push({0,ini});
    int pl=n;
    if(ini==n) pl=1;
    while(!q.empty())
    {
        pair<ll,int> 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(int ini)
{
    priority_queue<pair<ll,int>>q;
    q.push({0,ini});
    vector<ll> v(n+1,1e16);  
    int pl=n;
    if(ini==n) pl=1;
    while(!q.empty())
    {
        pair<ll,int> 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<int>ord1,ord2;
vector<int>B1,B2;
int cnt1=1,cnt2=1;
void P1(int node, int P)
{
    if(ord1[node]!=0) return;
    int ordent=cnt1;
    ord1[node]=cnt1++;
    for(auto i:GC1[node])
    {
        if(i.x!=P){
        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(int node, int P)
{
    if(ord2[node]!=0) return;
    int ordent=cnt2;
    ord2[node]=cnt2++;
    for(auto i:GC2[node])
    {
        if(i.x!=P)
        {
            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,int>>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++)
    {
        int 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=0; i<m; i++)
    {
        if(B1[i]==0&&B2[i]==0)
        {
            bs=min(bs,(min(DN[1],DN[A[i].y]+DT1[A[i].x]+C[i].x)+D1[A[i].y]+DTN[A[i].x]+C[i].x+C[i].y));
            bs=min(bs,(min(D1[n],D1[A[i].y]+DTN[A[i].x]+C[i].x)+DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y));
        }
    }
    for(int i=0; i<m; i++)
    {
        if(B1[i]==0&&B2[i]==0)continue;
        if(DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y<bs&&B1[i]==1)
        bs=min(bs,(CMC3(1,n,i)+DN[A[i].y]+DT1[A[i].x]+C[i].x+C[i].y));
        if(D1[A[i].y]+DTN[A[i].x]+C[i].x+C[i].y<bs&&B2[i]==1)
        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: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63