Submission #371607

#	Time	Username	Problem	Language	Result	Execution time	Memory
371607		Dymo	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	584 ms	13952 KiB

ho_t4

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
using namespace std;

#define ll  long long
#define ull  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn =2e5+30;
const ll mod=1e9+7 ;
const ll base=1e18;


ll x[maxn];
ll y[maxn];
ll c[maxn];
ll d[maxn];
vector<ll> adj[maxn][2];
ll dp[maxn][6];
ll pre[maxn];
ll n, m ;
bool dd[maxn];
bool in[maxn];

void dosth(ll p,ll type,ll ta,ll rc,ll t)
{
    /* priority_queue<pll,vector<pll>,greater<pll>> q;
     for (int i=1; i<=n; i++)
     {
         dp[i][type]=base;
     }
     dp[p][type]=0;
     q.push(make_pair(dp[p][type],p));
     while (!q.empty())
     {
         auto p=q.top();
         q.pop();
         ll u=p.ss;
         if (dp[u][type]!=p.ff)
             continue;
         for (auto to:adj[u][ta])
         {
             if (u==rc&&to==t)
                 continue;
             ll nxt=x[to]+y[to]-u;
             if (dp[nxt][type]>dp[u][type]+c[to])
             {
                 dp[nxt][type]=dp[u][type]+c[to];
                 q.push(make_pair(dp[nxt][type],nxt));
                 pre[nxt]=to;
             }
         }
     }*/
    for (int i=1; i<=n; i++)
    {
        dp[i][type]=base;
        in[i]=0;
    }
    dp[p][type]=0;
    for (int i=1; i<=n; i++)
    {
        ll min_d=base;
        ll minnd=1;
        for (int i=1; i<=n; i++)
        {
            if (in[i])
                continue;
            if (dp[i][type]<=min_d)
            {
                min_d=dp[i][type];
                minnd=i;
            }
        }
        in[minnd]=1;
        for (auto to:adj[minnd][ta])
        {
            if (minnd==rc&&to==t)
                continue;
            ll nxt= x[to]+y[to]-minnd;
            if (dp[nxt][type]>dp[minnd][type]+c[to])
            {
                dp[nxt][type]=dp[minnd][type]+c[to];
                pre[nxt]=to;
            }

        }


    }
}
ll ans=base;
void dosth1()
{
    dosth(1,0,0,-1,-1);
    ll nw=n;
    while (nw!=1)
    {
        //  cout <<nw<<" "<<pre[nw]<<endl;
        dd[pre[nw]]=1;
        //   cout <<pre[nw]<<endl;
        nw=x[pre[nw]]+y[pre[nw]]-nw;
    }
    dosth(1,1,1,-1,-1);
    dosth(n,2,0,-1,-1);
    dosth(n,3,1,-1,-1);
    ans=min(ans,dp[n][0]+dp[n][1]);
    for (int i=1; i<=m; i++)
    {
        if (dd[i])
        {
            ll h1=x[i];
            ll h2=y[i];
            adj[h2][0].pb(i);
            swap(x[i],y[i]);
            dosth(1,4,0,h1,i);
            ll h=dp[n][4]+d[i];
            dosth(n,4,0,h1,i);
            h+=dp[1][4];
            swap(x[i],y[i]);
            adj[h2][0].pop_back();


            ans=min(ans,h);
        }
        else
        {

            ans=min(ans,dp[n][0]+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]);
            /*  if (i==2)
              {
                  cout <<min(dp[n][0],dp[y[i]][0]+dp[x[i]][3]+c[i])+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]<<endl;
              }*/
            /*  if (min(dp[n][0],dp[y[i]][0]+dp[x[i]][3])+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]==1)
              {
                  cout <<i<<endl;
              }*/
        }
    }
}
void change()
{
    for (int i=1; i<=n; i++)
    {
        adj[i][0].clear();
        adj[i][1].clear();
    }
    for (int i=1; i<=m; i++)
    {
        if (x[i]==n)
            x[i]=1;
        else if (x[i]==1)
            x[i]=n;
        if (y[i]==n)
            y[i]=1;
        else if (y[i]==1)
            y[i]=n;
        // cout <<x[i]<< " "<<y[i]<<endl;
        adj[x[i]][0].pb(i);
        adj[y[i]][1].pb(i);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }

    cin>> n>> m;
    for (int i=1; i<=m; i++)
    {
        cin>>x[i]>> y[i]>>c[i]>> d[i ];
        adj[x[i]][0].pb(i);
        adj[y[i]][1].pb(i);
    }
    dosth(1,0,0,-1,-1);
    dosth(n,1,0,-1,-1);
    // cout <<dp[n][0]<<" "<<dp[1][1]<<endl;
    if (dp[n][0]!=base&&dp[1][1]!=base)
    {
        //  cout <<"?"<< " "<<endl;
        dosth1();
        change();
        dosth1();
        if (ans>=base)
        {
            ans=-1;
        }
        cout <<ans<<endl;

    }
    else if (dp[n][0]!=base)
    {
        dosth1();
        if (ans>=base)
        {
            ans=-1;
        }
        cout <<ans<<endl;
    }
    else if (dp[1][1]!=base)
    {
        change();
        dosth1();
        if (ans>=base)
        {
            ans=-1;
        }
        cout <<ans<<endl;
    }
    else
    {
        dosth(1,0,0,-1,-1);
        dosth(1,1,1,-1,-1);
        dosth(n,2,0,-1,-1);
        dosth(n,3,1,-1,-1);
        ll ans=dp[n][0]+dp[n][1];
        for (int i=1; i<=m; i++)
        {
            ans=min(ans,dp[y[i]][0]+dp[x[i]][3]+dp[y[i]][2]+dp[x[i]][1]+d[i]+2*c[i]);
        }
        if (ans>=base)
        {
            ans=-1;
        }
        cout <<ans;
    }





}

Compilation message (stderr)

ho_t4.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops, no-stack-protector")
      | 
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  175 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  176 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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