oj.uz

Submission #335647

# Submission time Handle Problem Language Result Execution time Memory
335647 2020-12-13T14:48:03 Z codebuster_10 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 490 ms 32180 KB 
#include <bits/stdc++.h>

using namespace std ;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define int long long 
#define ld long double
#define f(i,a,b) for(int i=a;i<b;++i)

#define endl '\n'
#define debug cout<<"\n========================================\n";
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;

#define PQ priority_queue
#define LB lower_bound  
#define UB upper_bound
#define fr first
#define sc second

#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define show(a) {for(auto xyz:a)cout<<xyz<<" ";cout<<endl;}
#define sz(x) (int)(x).size()

const int INF = 1e16 ;
vector<int> Dijkstra(int n,int src,vector< vector< array<int,2> > > &g){
  PQ<array<int,2> > q ;
  vector<int> dis(n, INF) ;
  dis[src] = 0 ;
  q.push({-dis[src],src}) ;
  while(sz(q)){
    int i = q.top()[1], k = -q.top()[0]  ;
    q.pop() ;
    if( k != dis[i] ){
      continue ;
    } 
    for(auto [j,w]:g[i]){
      if( dis[j] > dis[i] + w ){
        dis[j] = dis[i] + w ;
        q.push({-dis[j],j}) ;
      }
    }
  }
  return dis ;
}
signed main(){
  fastio;
  int N, M, S, T, U, V; 
  cin >> N >> M >> S >> T >> U >> V ;
  --S, --T, --U, --V;
  vector< vector< array<int,2> > > g(N) ;
  f(i,0,M){
    int a, b, c; cin >> a >> b >> c ;
    --a, --b;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  vector<int> disV = Dijkstra(N,V,g), disS = Dijkstra(N,S,g), disT = Dijkstra(N,T,g), disU = Dijkstra(N,U,g) ;
  vector<int> ComDisV = disV, ComDisV2 = disV  ;
  int MinDis = disT[S] ;
  
  vector< vector<int> > next(N), next2(N) ;
  f(i,0,N){
    for(auto [j, w]:g[i]){
      //does i->j works during S->T
      if( disS[i] + w + disT[j] == MinDis){
        next[i].push_back(j) ;
      }
      //does i->j works during T->S
      if( disT[i] + w + disS[j] == MinDis){
        next2[i].push_back(j) ;
      }
    }
  }
  PQ<array<int,2> > q ;
  f(i,0,N){
    if( sz(next[i]) ){
      q.push({-ComDisV[i], i}) ;
    }
  }
  while(sz(q)){
    int i = q.top()[1] , d = -q.top()[0] ;
    q.pop() ;
    if(d != ComDisV[i]){
      continue ;
    }
    for(auto j:next[i]){
      if(ComDisV[j] > ComDisV[i]){
        ComDisV[j] = ComDisV[i] ;
        q.push({-ComDisV[j], j}) ;
      }
    }
  }
  assert(sz(q) == 0) ;
  f(i,0,N){
    if( sz(next2[i]) ){
      q.push({-ComDisV2[i], i}) ;
    }
  }
  while(sz(q)){
    int i = q.top()[1] , d = -q.top()[0] ;
    q.pop() ;
    if(d != ComDisV2[i]){
      continue ;
    }
    for(auto j:next2[i]){
      if(ComDisV2[j] > ComDisV2[i]){
        ComDisV2[j] = ComDisV2[i] ;
        q.push({-ComDisV2[j], j}) ;
      }
    }
  }
  
  int ans = INF ;
  f(i,0,N){
    ans = min(ans, disU[i] + ComDisV2[i] ) ;
    ans = min(ans, disU[i] + ComDisV[i] ) ;
  }
  cout << ans ;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 22540 KB Output is correct
2 Correct 416 ms 24752 KB Output is correct
3 Correct 461 ms 29296 KB Output is correct
4 Correct 367 ms 22952 KB Output is correct
5 Correct 413 ms 27016 KB Output is correct
6 Correct 390 ms 22700 KB Output is correct
7 Correct 440 ms 27636 KB Output is correct
8 Correct 441 ms 27128 KB Output is correct
9 Correct 390 ms 22516 KB Output is correct
10 Correct 344 ms 22480 KB Output is correct
11 Correct 193 ms 20844 KB Output is correct
12 Correct 417 ms 22504 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 24488 KB Output is correct
2 Correct 448 ms 24988 KB Output is correct
3 Correct 434 ms 24304 KB Output is correct
4 Correct 431 ms 24692 KB Output is correct
5 Correct 452 ms 25748 KB Output is correct
6 Correct 472 ms 27564 KB Output is correct
7 Correct 477 ms 29088 KB Output is correct
8 Correct 436 ms 24944 KB Output is correct
9 Correct 459 ms 26096 KB Output is correct
10 Correct 426 ms 24560 KB Output is correct
11 Correct 225 ms 22124 KB Output is correct
12 Correct 456 ms 27652 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1772 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 16 ms 3052 KB Output is correct
5 Correct 8 ms 1644 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 8 ms 1772 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 22540 KB Output is correct
2 Correct 416 ms 24752 KB Output is correct
3 Correct 461 ms 29296 KB Output is correct
4 Correct 367 ms 22952 KB Output is correct
5 Correct 413 ms 27016 KB Output is correct
6 Correct 390 ms 22700 KB Output is correct
7 Correct 440 ms 27636 KB Output is correct
8 Correct 441 ms 27128 KB Output is correct
9 Correct 390 ms 22516 KB Output is correct
10 Correct 344 ms 22480 KB Output is correct
11 Correct 193 ms 20844 KB Output is correct
12 Correct 417 ms 22504 KB Output is correct
13 Correct 443 ms 24488 KB Output is correct
14 Correct 448 ms 24988 KB Output is correct
15 Correct 434 ms 24304 KB Output is correct
16 Correct 431 ms 24692 KB Output is correct
17 Correct 452 ms 25748 KB Output is correct
18 Correct 472 ms 27564 KB Output is correct
19 Correct 477 ms 29088 KB Output is correct
20 Correct 436 ms 24944 KB Output is correct
21 Correct 459 ms 26096 KB Output is correct
22 Correct 426 ms 24560 KB Output is correct
23 Correct 225 ms 22124 KB Output is correct
24 Correct 456 ms 27652 KB Output is correct
25 Correct 9 ms 1772 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 16 ms 3052 KB Output is correct
29 Correct 8 ms 1644 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 2 ms 620 KB Output is correct
33 Correct 1 ms 492 KB Output is correct
34 Correct 8 ms 1772 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 1 ms 364 KB Output is correct
39 Correct 1 ms 492 KB Output is correct
40 Correct 362 ms 21596 KB Output is correct
41 Correct 384 ms 22588 KB Output is correct
42 Correct 379 ms 22744 KB Output is correct
43 Correct 275 ms 25440 KB Output is correct
44 Correct 270 ms 25440 KB Output is correct
45 Correct 490 ms 32164 KB Output is correct
46 Correct 479 ms 32168 KB Output is correct
47 Correct 380 ms 22980 KB Output is correct
48 Correct 317 ms 25440 KB Output is correct
49 Correct 310 ms 21588 KB Output is correct
50 Correct 463 ms 30664 KB Output is correct
51 Correct 470 ms 32180 KB Output is correct