oj.uz

Submission #923455

# Submission time Handle Problem Language Result Execution time Memory
923455 2024-02-07T09:11:19 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 4964 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));
  }
};

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]=LLONG_MAX;
        }
    }
    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_set<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({y,c});
        v[y].insert({x,c});
        int curd[n];
        for(int i=0;i<n;i++){
            curd[i]=LLONG_MAX;
        }
        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]==LLONG_MAX){
            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]=LLONG_MAX;
        }
        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]!=LLONG_MAX){
            ansnow+=curd[0]+d;
            ans=min(ans,ansnow);
        }
        //cerr<<ansnow<<"\n\n";
        v[y].erase({x,c});
        v[x].insert({y,c});
    }
    if(ans<LLONG_MAX-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 18 ms 604 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 81 ms 856 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 19 ms 600 KB Output is correct
7 Correct 1 ms 600 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 37 ms 720 KB Output is correct
12 Correct 33 ms 868 KB Output is correct
13 Correct 74 ms 876 KB Output is correct
14 Correct 70 ms 816 KB Output is correct
15 Correct 53 ms 860 KB Output is correct
16 Correct 78 ms 860 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 3672 KB Output is correct
2 Correct 985 ms 4784 KB Output is correct
3 Correct 593 ms 4964 KB Output is correct
4 Incorrect 49 ms 924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 15 ms 816 KB Output is correct
3 Correct 20 ms 3972 KB Output is correct
4 Correct 16 ms 600 KB Output is correct
5 Correct 24 ms 4820 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Execution timed out 1077 ms 4692 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 18 ms 604 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 81 ms 856 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 19 ms 600 KB Output is correct
7 Correct 1 ms 600 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 37 ms 720 KB Output is correct
12 Correct 33 ms 868 KB Output is correct
13 Correct 74 ms 876 KB Output is correct
14 Correct 70 ms 816 KB Output is correct
15 Correct 53 ms 860 KB Output is correct
16 Correct 78 ms 860 KB Output is correct
17 Correct 817 ms 3672 KB Output is correct
18 Correct 985 ms 4784 KB Output is correct
19 Correct 593 ms 4964 KB Output is correct
20 Incorrect 49 ms 924 KB Output isn't correct
21 Halted 0 ms 0 KB -