oj.uz

Submission #922822

# Submission time Handle Problem Language Result Execution time Memory
922822 2024-02-06T07:14:32 Z vjudge1 Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 15536 KB 
// Отче наш, сущий на небесах! Да святится имя Твое; да приидет Царствие Твое; да будет воля Твоя и на земле, как на небе; хлеб наш насущный подавай нам на каждый день; и прости нам грехи наши, ибо и мы прощаем всякому должнику нашему; и не введи нас в искушение, но избавь нас от лукавого ML, TL, WA
#include <bits/stdc++.h>

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

#define ll long long
#define ld long double
#define pii pair<int,int>
#define F first
#define S second
#define in insert
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz(s) (int)s.size()
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))
#define lb lower_bound
#define ub upper_bound
#define int ll

using namespace std;

const int MAX=2e5+10;
const int N=1000+10;
const int inf=1e18;
const int mod=1e9+9;
const int B=2003;
const ld eps=1e-9;

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

int binpow(int a,int n){
  if(n==0)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return (k*k)%mod;
}

int n,m;
int a[MAX],b[MAX],c[MAX],dd[MAX];
vector<pii> g[MAX];
int d[MAX],d1[MAX];

int calc(int reb){
  for(int i=1;i<=n;i++){
    g[i].clear();
    d[i]=inf;
    d1[i]=inf;
  }
  for(int i=1;i<=m;i++){
    if(i==reb){
      g[b[i]].pb({a[i],c[i]});
    }
    else{
      g[a[i]].pb({b[i],c[i]});
    }
  }
  d[1]=0;
  priority_queue<pii> q;
  q.push({0,1});
  while(!q.empty()){
    int v=q.top().S;
    int w=q.top().F;
    q.pop();
    if(w+d[v]!=0)continue;
    for(auto to:g[v]){
      if(d[to.F]>d[v]+to.S){
        d[to.F]=d[v]+to.S;
        q.push({-d[to.F],to.F});
      }
    }
  }
  d1[n]=0;
  q.push({0,n});
  while(!q.empty()){
    int v=q.top().S;
    int w=q.top().F;
    q.pop();
    if(w+d1[v]!=0)continue;
    for(auto to:g[v]){
      if(d1[to.F]>d1[v]+to.S){
        d1[to.F]=d1[v]+to.S;
        q.push({-d1[to.F],to.F});
      }
    }
  }  
  return d[n]+d1[1];
}

void solve(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>a[i]>>b[i]>>c[i]>>dd[i];
  }
  int ans=inf;
  for(int i=0;i<=m;i++){
    ans=min(ans,calc(i)+dd[i]);
    // cout<<i<<" "<<calc(i)<<"\n";
  }
  if(ans==inf)cout<<-1;
  else cout<<ans;
}

signed main(){
  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:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize("Ofast")
      | 
ho_t4.cpp:5: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    5 | #pragma target("avx2")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12824 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 43 ms 12636 KB Output is correct
4 Correct 45 ms 12808 KB Output is correct
5 Correct 17 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 12 ms 12636 KB Output is correct
10 Correct 68 ms 12800 KB Output is correct
11 Correct 63 ms 12804 KB Output is correct
12 Correct 69 ms 12800 KB Output is correct
13 Correct 26 ms 12892 KB Output is correct
14 Correct 29 ms 12636 KB Output is correct
15 Correct 26 ms 12892 KB Output is correct
16 Correct 29 ms 12828 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 15536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12796 KB Output is correct
2 Correct 4 ms 12632 KB Output is correct
3 Execution timed out 1088 ms 13824 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12824 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 43 ms 12636 KB Output is correct
4 Correct 45 ms 12808 KB Output is correct
5 Correct 17 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 12 ms 12636 KB Output is correct
10 Correct 68 ms 12800 KB Output is correct
11 Correct 63 ms 12804 KB Output is correct
12 Correct 69 ms 12800 KB Output is correct
13 Correct 26 ms 12892 KB Output is correct
14 Correct 29 ms 12636 KB Output is correct
15 Correct 26 ms 12892 KB Output is correct
16 Correct 29 ms 12828 KB Output is correct
17 Execution timed out 1012 ms 15536 KB Time limit exceeded
18 Halted 0 ms 0 KB -