oj.uz

Submission #922793

# Submission time Handle Problem Language Result Execution time Memory
922793 2024-02-06T06:39:34 Z vjudge1 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 511 ms 262144 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define int ll
#define y1 yy
#define ppb pop_back
#define gcd(a,b) __gcd(a,b)
#define in insert

const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};

const int inf=1e18;
const int N=5e4+3;
const int MAX=210;
const int mod=1e9+7;


int n,m;
vector<pair<int,pii>> g[MAX];
int d[MAX][N+N];
int d1[MAX][N+N];

void solve(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v,c,d;
    cin>>u>>v>>c>>d;
    g[u].pb({v,{c,i+m}});
    g[v].pb({u,{c+d,i}});
  }
  {
    for(int i=1;i<=n;i++){
      for(int j=0;j<=m;j++){
        d[i][j]=inf;
      }
    }
    set<pair<int,pii>> st;
    for(int j=0;j<=m;j++){
      d[1][j]=0;
      st.in({d[1][j],{1,j}});
    }
    while(!st.empty()){
      int v=st.begin()->S.F;
      int r=st.begin()->S.S;
      st.erase(st.begin());
      for(auto to:g[v]){
        if(to.S.S>m){
          if(to.S.S-m==r)continue;
          if(d[to.F][r]>d[v][r]+to.S.F){
            st.erase({d[to.F][r],{to.F,r}});
            d[to.F][r]=d[v][r]+to.S.F;
            st.in({d[to.F][r],{to.F,r}});
          }
        }
        else{
          if(to.S.S!=r)continue;
          if(d[to.F][r]>d[v][r]+to.S.F){
            st.erase({d[to.F][r],{to.F,r}});
            d[to.F][r]=d[v][r]+to.S.F;
            st.in({d[to.F][r],{to.F,r}});
          }
        }
      }
    }
  }
  {
    for(int i=1;i<=n;i++){
      for(int j=0;j<=m;j++){
        d1[i][j]=inf;
      }
    }
    set<pair<int,pii>> st;
    for(int j=0;j<=m;j++){
      d1[n][j]=0;
      st.in({d1[n][j],{n,j}});
    }
    while(!st.empty()){
      int v=st.begin()->S.F;
      int r=st.begin()->S.S;
      st.erase(st.begin());
      for(auto to:g[v]){
        if(to.S.S>m){
          if(to.S.S-m==r)continue;
          if(d1[to.F][r]>d1[v][r]+to.S.F){
            st.erase({d1[to.F][r],{to.F,r}});
            d1[to.F][r]=d1[v][r]+to.S.F;
            st.in({d1[to.F][r],{to.F,r}});
          }
        }
        else{
          if(to.S.S!=r)continue;
          if(d1[to.F][r]>d1[v][r]+to.S.F){
            st.erase({d1[to.F][r],{to.F,r}});
            d1[to.F][r]=d1[v][r]+to.S.F;
            st.in({d1[to.F][r],{to.F,r}});
          }
        }
      }
    }
  }
  int ans=d[n][0]+d1[1][0];
  for(int i=1;i<=m;i++){
    ans=min(ans,d[n][i]+d1[1][i]);
  }
  if(ans<inf)cout<<ans<<"\n";
  else cout<<-1<<"\n";
}

main(){
  // freopen("prizes.in", "r", stdin);
  // freopen("prizes.out", "w", stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

ho_t4.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  124 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 171088 KB Output is correct
2 Correct 20 ms 163848 KB Output is correct
3 Correct 136 ms 171304 KB Output is correct
4 Correct 146 ms 211508 KB Output is correct
5 Correct 48 ms 55884 KB Output is correct
6 Correct 27 ms 208732 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 6 ms 4656 KB Output is correct
10 Correct 208 ms 211796 KB Output is correct
11 Correct 197 ms 223568 KB Output is correct
12 Correct 205 ms 223824 KB Output is correct
13 Incorrect 86 ms 222244 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 511 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 228000 KB Output is correct
2 Correct 28 ms 221184 KB Output is correct
3 Runtime error 439 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 171088 KB Output is correct
2 Correct 20 ms 163848 KB Output is correct
3 Correct 136 ms 171304 KB Output is correct
4 Correct 146 ms 211508 KB Output is correct
5 Correct 48 ms 55884 KB Output is correct
6 Correct 27 ms 208732 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 6 ms 4656 KB Output is correct
10 Correct 208 ms 211796 KB Output is correct
11 Correct 197 ms 223568 KB Output is correct
12 Correct 205 ms 223824 KB Output is correct
13 Incorrect 86 ms 222244 KB Output isn't correct
14 Halted 0 ms 0 KB -