oj.uz

Submission #923467

# Submission time Handle Problem Language Result Execution time Memory
923467 2024-02-07T09:30:39 Z noyancanturk Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 4052 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_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]=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({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 16 ms 604 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 81 ms 860 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 1 ms 348 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 30 ms 860 KB Output is correct
11 Correct 34 ms 856 KB Output is correct
12 Correct 32 ms 856 KB Output is correct
13 Correct 69 ms 856 KB Output is correct
14 Correct 71 ms 1108 KB Output is correct
15 Correct 53 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 Correct 820 ms 4052 KB Output is correct
2 Correct 998 ms 3916 KB Output is correct
3 Correct 590 ms 3924 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 856 KB Output is correct
2 Correct 15 ms 604 KB Output is correct
3 Correct 17 ms 3416 KB Output is correct
4 Correct 20 ms 804 KB Output is correct
5 Correct 21 ms 3868 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Execution timed out 1061 ms 3768 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 16 ms 604 KB Output is correct
3 Correct 73 ms 860 KB Output is correct
4 Correct 81 ms 860 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 1 ms 348 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 30 ms 860 KB Output is correct
11 Correct 34 ms 856 KB Output is correct
12 Correct 32 ms 856 KB Output is correct
13 Correct 69 ms 856 KB Output is correct
14 Correct 71 ms 1108 KB Output is correct
15 Correct 53 ms 856 KB Output is correct
16 Correct 77 ms 860 KB Output is correct
17 Correct 820 ms 4052 KB Output is correct
18 Correct 998 ms 3916 KB Output is correct
19 Correct 590 ms 3924 KB Output is correct
20 Incorrect 48 ms 860 KB Output isn't correct
21 Halted 0 ms 0 KB -