Submission #1127186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127186		Szymon_Pilipczuk	Olympic Bus (JOI20_ho_t4)	C++20	16 / 100	474 ms	15204 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
long long k[50000][4];
long long inf = (long long)1000000000*1000000000;
long long dis[4][200][2];
map<vector<long long>,int> kr;
vector<vector<vector<long long>>> gr[2];
priority_queue<vector<long long>> pq;
void dk(long long v,long long c,long long p,long long p2)
{
    for(int i = 0;i<gr[p2][v].size();i++)
    {
        if(dis[p][gr[p2][v][i][0]][0] > c+gr[p2][v][i][1] ||(dis[p][gr[p2][v][i][0]][0] >= c+gr[p2][v][i][1] && k[dis[p][gr[p2][v][i][0]][1]][3] > gr[p2][v][i][2]))
        {
            pq.push({-1*(c+gr[p2][v][i][1]),gr[p2][v][i][0],p,p2});
            dis[p][gr[p2][v][i][0]][0] = gr[p2][v][i][1]+c;
            if(p2 == 0)
            {
                dis[p][gr[p2][v][i][0]][1] = kr[{v,gr[p2][v][i][0],gr[p2][v][i][1],gr[p2][v][i][2]}];
            }
            else
            {
                dis[p][gr[p2][v][i][0]][1] = kr[{gr[p2][v][i][0],v,gr[p2][v][i][1],gr[p2][v][i][2]}];
            }

        }
    }
}
priority_queue<vector<long long>> pq2;
long long dis2[200];
void dk2(long long c,long long v)
{
    for(int i = 0;i<gr[0][v].size();i++)
    {
        if(dis2[gr[0][v][i][0]] > c+gr[0][v][i][1])
        {
            pq2.push({-1*(c+gr[0][v][i][1]),gr[0][v][i][0]});
            dis2[gr[0][v][i][0]] = c+gr[0][v][i][1];
        }
    }
}
void del()
{
    for(int i = 0;i<200;i++)
    {
        dis2[i] = inf;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    gr[0].resize(n);
    gr[1].resize(n);
    for(int i = 0;i<4;i++)
    {
        for(int j = 0;j<n;j++)
        {
            dis[i][j][0] = inf;
            dis[i][j][1] = -1;
        }
    }
    for(int i = 0;i<m;i++)
    {
        long long u,v,c,d;
        cin>>u>>v>>c>>d;
        u--;v--;
        kr[{u,v,c,d}] = i;
        gr[0][u].push_back({v,c,d});
        gr[1][v].push_back({u,c,d});
        k[i][0] = u;
        k[i][1] = v;
        k[i][2] = c;
        k[i][3] = d;
    }
    pq.push({0,0,0,0});
    pq.push({0,0,1,1});
    pq.push({0,n-1,2,0});
    pq.push({0,n-1,3,1});
    while(!pq.empty())
    {
        long long a,b,c,d;
        a = pq.top()[1];
        b = pq.top()[0]*-1;
        c = pq.top()[2];
        d = pq.top()[3];
        pq.pop();
        if(dis[c][a][0] >= b)
        {
            dk(a,b,c,d);
        }


    }
    set<long long> sps;
    for(int i = 0;i<2;i++)
    {
        for(int j = 1;j<n;j++)
        {
            if(dis[i][j][1] != -1)
            {
                sps.insert(dis[i][j][1]);
            }
        }
    }
    for(int i = 2;i<4;i++)
    {
        for(int j = 0;j<n-1;j++)
        {
            if(dis[i][j][1] != -1)
            {
                sps.insert(dis[i][j][1]);
            }
        }
    }
    long long ans = dis[0][n-1][0]+dis[2][0][0];
    dis[2][n-1][0] = 0;
    dis[3][n-1][0] = 0;
    dis[0][0][0] = 0;
    dis[1][0][0] = 0;
    for(int i = 0;i<m;i++)
    {
        if(sps.find(i) == sps.end())
        {
            ans = min(ans,k[i][3]+min(dis[0][n-1][0],dis[0][k[i][1]][0]+k[i][2]+dis[3][k[i][0]][0])+min(dis[2][0][0],dis[2][k[i][1]][0]+k[i][2]+dis[1][k[i][0]][0]));
        }
    }
    del();
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<gr[0][i].size();j++)
        {
            if(sps.find(kr[{i,gr[0][i][j][0],gr[0][i][j][1],gr[0][i][j][2]}]) != sps.end())
            {
                long long cu = gr[0][i][j][0];
                long long cans = gr[0][i][j][2];
                gr[0][i][j][0] = i;
                gr[0][cu].push_back({i,gr[0][i][j][1]});
                pq2.push({0,0});
                while(!pq2.empty())
                {
                    long long a = pq2.top()[0]*-1,b = pq2.top()[1];
                    pq2.pop();
                    if(dis2[b] >= a)
                    {
                        dk2(a,b);
                    }
                }
                cans += dis2[n-1];
                del();
                pq2.push({0,n-1});
                while(!pq2.empty())
                {
                    long long a = pq2.top()[0]*-1,b = pq2.top()[1];
                    pq2.pop();
                    if(dis2[b] >= a)
                    {
                        dk2(a,b);
                    }

                }
                cans+=dis2[0];
                del();
                gr[0][i][j][0] = cu;
                gr[0][cu].pop_back();
                ans = min(ans,cans);
            }
        }
    }
    if(ans >= inf)
    {
        cout<<-1;
    }
    else
    {
        cout<<ans;
    }
}

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