제출 #371600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371600		Dymo	Olympic Bus (JOI20_ho_t4)	C++14	37 / 100	1086 ms	14060 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];

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;
            }
        }
    }

}
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("test.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 <<"?";
        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;
    }





}

컴파일 시 표준 에러 (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:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  139 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  140 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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