oj.uz

Submission #923517

# Submission time Handle Problem Language Result Execution time Memory
923517 2024-02-07T11:12:12 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 4048 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 16 ms 604 KB Output is correct
3 Correct 74 ms 860 KB Output is correct
4 Correct 80 ms 856 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 19 ms 604 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 804 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 856 KB Output is correct
14 Correct 70 ms 860 KB Output is correct
15 Correct 53 ms 860 KB Output is correct
16 Correct 78 ms 856 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 3820 KB Output is correct
2 Correct 1000 ms 3816 KB Output is correct
3 Correct 585 ms 4048 KB Output is correct
4 Incorrect 48 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 860 KB Output is correct
2 Correct 15 ms 816 KB Output is correct
3 Correct 17 ms 3420 KB Output is correct
4 Correct 16 ms 604 KB Output is correct
5 Correct 20 ms 3860 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Execution timed out 1094 ms 3772 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 604 KB Output is correct
3 Correct 74 ms 860 KB Output is correct
4 Correct 80 ms 856 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 19 ms 604 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 804 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 856 KB Output is correct
14 Correct 70 ms 860 KB Output is correct
15 Correct 53 ms 860 KB Output is correct
16 Correct 78 ms 856 KB Output is correct
17 Correct 824 ms 3820 KB Output is correct
18 Correct 1000 ms 3816 KB Output is correct
19 Correct 585 ms 4048 KB Output is correct
20 Incorrect 48 ms 860 KB Output isn't correct
21 Halted 0 ms 0 KB -