oj.uz

Submission #923514

# Submission time Handle Problem Language Result Execution time Memory
923514 2024-02-07T11:08:14 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 5308 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{
    return hash<int>()(k.first^(k.second<<10));
    }
};
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 860 KB Output is correct
2 Correct 17 ms 780 KB Output is correct
3 Correct 74 ms 860 KB Output is correct
4 Correct 81 ms 856 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 20 ms 672 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 31 ms 796 KB Output is correct
11 Correct 33 ms 860 KB Output is correct
12 Correct 32 ms 860 KB Output is correct
13 Correct 70 ms 860 KB Output is correct
14 Correct 71 ms 860 KB Output is correct
15 Correct 54 ms 856 KB Output is correct
16 Correct 79 ms 856 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 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 6 ms 856 KB Output is correct
2 Correct 16 ms 600 KB Output is correct
3 Correct 18 ms 4188 KB Output is correct
4 Correct 17 ms 812 KB Output is correct
5 Correct 21 ms 5228 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 1008 ms 5308 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 860 KB Output is correct
2 Correct 17 ms 780 KB Output is correct
3 Correct 74 ms 860 KB Output is correct
4 Correct 81 ms 856 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 20 ms 672 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 31 ms 796 KB Output is correct
11 Correct 33 ms 860 KB Output is correct
12 Correct 32 ms 860 KB Output is correct
13 Correct 70 ms 860 KB Output is correct
14 Correct 71 ms 860 KB Output is correct
15 Correct 54 ms 856 KB Output is correct
16 Correct 79 ms 856 KB Output is correct
17 Execution timed out 1036 ms 5212 KB Time limit exceeded
18 Halted 0 ms 0 KB -