Submission #226476

#	Time	Username	Problem	Language	Result	Execution time	Memory
226476		thebes	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	364 ms	162656 KiB

ho_t4

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
#define pb push_back

const int MN = 202, MM = 5e4+5;
int N, M, i, j, x, y, w[MM], c[MM], u[MM], vs[MN], ban[MM], par[MN]; ll ans, dis[MN], a[MM][MN], b[MM][MN], cost[MM];
vector<pii> adj[MN], rev[MN];
vi tree; pii ed[MM];

void dij(int src,bool dir){
    memset(par,-1,sizeof(par));
    memset(vs,0,sizeof(vs));
    for(i=1;i<=N;i++)
        dis[i]=1LL<<55;
    dis[src]=0;
    int cur=src; ll mn;
    while(cur!=-1){
        vs[cur]=1;
        if(dir==1){
            for(auto v : adj[cur]){
                if(ban[v.second]) continue;
                if(dis[cur]+w[v.second]<dis[v.first]){
                    dis[v.first]=dis[cur]+w[v.second];
                    par[v.first]=v.second;
                }
            }
        }
        else{
            for(auto v : rev[cur]){
                if(ban[v.second]) continue;
                if(dis[cur]+w[v.second]<dis[v.first]){
                    dis[v.first]=dis[cur]+w[v.second];
                    par[v.first]=v.second;
                }
            }
        }
        mn=1LL<<50; cur=-1;
        for(i=1;i<=N;i++){
            if(vs[i]) continue;
            if(dis[i]<mn){
                mn=dis[i];
                cur=i;
            }
        }
    }
    for(i=1;i<=N;i++){
        if(par[i]!=-1) u[par[i]]=1;
    }
}

int main(){
    mt19937 mt(time(0));
    for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
        scanf("%d%d%d%d",&x,&y,&w[i],&c[i]);
        ed[i]={x,y};
        adj[x].pb({y,i});
        rev[y].pb({x,i});
    }
    for(i=1;i<=N;i++){
        shuffle(adj[i].begin(),adj[i].end(),mt);
        shuffle(rev[i].begin(),rev[i].end(),mt);
    }
    for(int k=0;k<2;k++){
        memset(u,0,sizeof(u));
        dij(1,1^k);
        tree.clear();
        for(i=1;i<=M;i++){
            if(u[i]) tree.pb(i);
            else{
                for(j=1;j<=N;j++)
                    a[i][j]=dis[j];
            }
        }
        assert(tree.size()<=N);
        for(auto v : tree){
            ban[v]=1;
            dij(1,1^k);
            for(j=1;j<=N;j++)
                a[v][j]=dis[j];
            ban[v]=0;
        }
        memset(u,0,sizeof(u));
        dij(N,k);
        tree.clear();
        for(i=1;i<=M;i++){
            if(u[i]) tree.pb(i);
            else{
                for(j=1;j<=N;j++)
                    b[i][j]=dis[j];
            }
        }
        assert(tree.size()<=N);
        for(auto v : tree){
            ban[v]=1;
            dij(N,k);
            for(j=1;j<=N;j++)
                b[v][j]=dis[j];
            ban[v]=0;
        }
        for(j=1;j<=M;j++){
            if(!k) cost[j]+=min(a[j][N],a[j][ed[j].second]+w[j]+b[j][ed[j].first]);
            else cost[j]+=min(a[j][N],a[j][ed[j].first]+w[j]+b[j][ed[j].second]);
        }
    }
    dij(1,1);
    ans+=dis[N];
    dij(N,1);
    ans+=dis[1];
    for(j=1;j<=M;j++)
        ans=min(ans,cost[j]+c[j]);
    if(ans>(1LL<<50)) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from ho_t4.cpp:1:
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(tree.size()<=N);
                ~~~~~~~~~~~^~~
ho_t4.cpp:97:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(tree.size()<=N);
                ~~~~~~~~~~~^~~
ho_t4.cpp:58:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
         ~~~~~~~~~~~~~~~~~~~^~~~
ho_t4.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&x,&y,&w[i],&c[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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