oj.uz

Submission #923518

# Submission time Handle Problem Language Result Execution time Memory
923518 2024-02-07T11:12:56 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 5304 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+5;
#else
    const int lim=3e3+3;
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int uint64_t
#define pb push_back
    
const int mod=1e9+7;
//const int mod=(1ll<<61)-1;
using pii=pair<int,int>;
    
struct edge{
    int x,y,c,d;
};
    
template <>
struct std::hash<pii>{
    size_t operator()(const pii& k) const{
        int first=hash<int>()(k.first),second=hash<int>()(k.second);
        return hash<int>()(first^second);
    }
};
const int inf=INT_MAX*200ll;
inline void solve(){
    int n,m;
    cin>>n>>m;
    edge all[m];
    for(int i=0;i<m;i++){
        cin>>all[i].x>>all[i].y>>all[i].c>>all[i].d;
        all[i].x--,all[i].y--;
    }
    int dist[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=inf;
        }
    }
    for(int i=0;i<m;i++){
        dist[all[i].x][all[i].y]=min(
            all[i].c,
            dist[all[i].x][all[i].y]
        );
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dist[i][j]=min(
                    dist[i][j],
                    dist[i][k]+dist[k][j]
                );
            }
        }
    }
    unordered_multiset<pii>v[n];
    for(int i=0;i<m;i++){
        v[all[i].x].insert(pii(all[i].y,all[i].c));
    }
    int ans=dist[0][n-1]+dist[n-1][0];
    //cerr<<ans<<"\n";
    for(auto[x,y,c,d]:all){
        //cerr<<x<<" "<<y<<" "<<c<<" "<<dist[y][x]<<"\n";
        if(dist[y][x]<=c)continue; // better upperbound exists
        v[x].erase(v[x].find({y,c}));
        v[y].insert({x,c});
        int curd[n];
        for(int i=0;i<n;i++){
            curd[i]=inf;
        }
        curd[0]=0;
        bool vis[n];
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n-1;i++){
            int mini=-1;
            for(int j=0;j<n;j++){
                if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
                    mini=j;
                }
            }
            vis[mini]=1;
            if(mini==n-1)break;
            for(pii ed:v[mini]){
                curd[ed.first]=min(
                    curd[ed.first],
                    curd[mini]+ed.second
                );
            }
        }
        if(curd[n-1]==inf){
            v[y].erase({x,c});
            v[x].insert({y,c});
            continue;
        }
        //for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        //cerr<<"\n";
        int ansnow=curd[n-1];
        for(int i=0;i<n;i++){
            curd[i]=inf;
        }
        curd[n-1]=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n-1;i++){
            int mini=-1;
            for(int j=0;j<n;j++){
                if(!vis[j]&&(~mini?(curd[j]<curd[mini]):1)){
                    mini=j;
                }
            }
            vis[mini]=1;
            if(!mini)break;
            for(pii ed:v[mini]){
                curd[ed.first]=min(
                    curd[ed.first],
                    curd[mini]+ed.second
                );
            }
        }
        //for(int i=0;i<n;i++)cerr<<curd[i]<<" ";
        //cerr<<"\n";
        if(curd[0]!=inf){
            ansnow+=curd[0]+d;
            ans=min(ans,ansnow);
        }
        //cerr<<ansnow<<"\n\n";
        v[y].erase(v[y].find({x,c}));
        v[x].insert({y,c});
    }
    if(ans<inf-100)cout<<ans<<"\n";
    else cout<<"-1\n";
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 856 KB Output is correct
2 Correct 16 ms 812 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 80 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 19 ms 632 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 30 ms 856 KB Output is correct
11 Correct 33 ms 860 KB Output is correct
12 Correct 32 ms 856 KB Output is correct
13 Correct 77 ms 860 KB Output is correct
14 Correct 70 ms 856 KB Output is correct
15 Correct 55 ms 856 KB Output is correct
16 Correct 77 ms 860 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 5212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 15 ms 600 KB Output is correct
3 Correct 18 ms 4032 KB Output is correct
4 Correct 17 ms 604 KB Output is correct
5 Correct 21 ms 5012 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1020 ms 5304 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 856 KB Output is correct
2 Correct 16 ms 812 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 80 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 19 ms 632 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 30 ms 856 KB Output is correct
11 Correct 33 ms 860 KB Output is correct
12 Correct 32 ms 856 KB Output is correct
13 Correct 77 ms 860 KB Output is correct
14 Correct 70 ms 856 KB Output is correct
15 Correct 55 ms 856 KB Output is correct
16 Correct 77 ms 860 KB Output is correct
17 Execution timed out 1052 ms 5212 KB Time limit exceeded
18 Halted 0 ms 0 KB -