oj.uz

Submission #518497

# Submission time Handle Problem Language Result Execution time Memory
518497 2022-01-24T00:06:13 Z vijay Commuter Pass (JOI18_commuter_pass) C++17
39 / 100
 720 ms 35104 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <string>
#include <climits>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <assert.h>
using namespace std;

using ll = long long;
#define pb push_back
#define mp make_pair

int n, m, s, t, u, v;
vector<vector<pair<int, int> > > adj; // cost first, then position

vector<int> dist(int start, vector<vector<pair<int, int> > > adj){
  vector<int> ret(n, -1);
  priority_queue<pair<ll, pair<int, int> >, vector<pair<ll, pair<int, int> > >, greater<pair<ll, pair<int, int> > > > pq;
  pq.push(mp(0, mp(start, -1)));
  while(!pq.empty()){
    pair<ll, pair<int, int> > curr = pq.top(); pq.pop();
    if(ret[curr.second.first] != -1){
      continue;
    }
    ret[curr.second.first] = curr.first;

    for(auto& edge: adj[curr.second.first]){
      pq.push(mp(edge.first + curr.first, mp(edge.second, curr.second.first)));
    }
  }
  return ret;
}

vector<int> prev(int start, vector<vector<pair<int, int> > > adj){
  vector<int> ret(n, -1);
  priority_queue<pair<ll, pair<int, int> >, vector<pair<ll, pair<int, int> > >, greater<pair<ll, pair<int, int> > > > pq;
  pq.push(mp(0, mp(start, -1)));
  while(!pq.empty()){
    pair<ll, pair<int, int> > curr = pq.top(); pq.pop();
    if(ret[curr.second.first] != -1){
      continue;
    }
    ret[curr.second.first] = curr.second.second;

    for(auto& edge: adj[curr.second.first]){
      pq.push(mp(edge.first + curr.first, mp(edge.second, curr.second.first)));
    }
  }
  return ret;
}


int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  // ifstream cin;
  // cin.open("test.in");

  cin >> n >> m >> s >> t >> u >> v;
  adj.resize(n);
  for(int i = 0; i < m; i++){
    int a, b, c; cin >> a >> b >> c; a--; b--;
    adj[a].pb(mp(c, b));
    adj[b].pb(mp(c, a));
  }
  s--; t--; u--; v--;

  // figure out, with the option to have gone on the train
  vector<int> sdist = dist(s, adj);
  vector<int> sprev = prev(s, adj);
  vector<int> tdist = dist(t, adj);
  vector<int> tprev = prev(t, adj);

  // cout << "sdist: ";
  // for(int i = 0; i < n; i++){
  //   cout << sdist[i] << " ";
  // }
  // cout << "\n";
  //
  // cout << "tdist: ";
  // for(int i = 0; i < n; i++){
  //   cout << tdist[i] << " ";
  // }
  // cout << "\n";

  vector<vector<bool> > visited(n, vector<bool>(4, false));
  // 0 - haven't done it
  // 1 - doing it
  // 2 - already done it

  priority_queue<pair<ll, pair<int, int> >, vector<pair<ll, pair<int, int> > >, greater<pair<ll, pair<int, int> > > > pq; // <distance, <pos, 0-1-2> >
  pq.push(mp(0, mp(u, 0)));

  while(!pq.empty()){
    pair<ll, pair<int, int> > curr = pq.top(); pq.pop();
    if(visited[curr.second.first][curr.second.second]){
      continue;
    }
    visited[curr.second.first][curr.second.second] = true;

    // cout << "minimum distance " << (curr.second.first + 1) << " " << curr.second.second << " " << " is " << curr.first << "\n";

    if(curr.second.first == v){
      cout << curr.first << "\n";
      return 0;
    }


    for(auto& edge: adj[curr.second.first]){
      bool isOnPath = (edge.first + sdist[edge.second] + tdist[curr.second.first]) == sdist[t] || (edge.first + sdist[curr.second.first] + tdist[edge.second] == tdist[s]);
      if(curr.second.second == 0){ // haven't started
        if(isOnPath && tdist[edge.second] < tdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 1)));
        }
        if(isOnPath && sdist[edge.second] < sdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 2)));
        }
        pq.push(mp(curr.first + edge.first, mp(edge.second, 0)));
      } else if (curr.second.second == 1){ // moving to t
        if(isOnPath && tdist[edge.second] < tdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 1)));
        } else {
          pq.push(mp(curr.first + edge.first, mp(edge.second, 3)));
        }
      } else if (curr.second.second == 2){ // moving to s
        // is the distance from
        if(isOnPath && sdist[edge.second] < sdist[curr.second.first]){
          pq.push(mp(curr.first, mp(edge.second, 2)));
        } else {
          pq.push(mp(curr.first + edge.first, mp(edge.second, 3)));
        }
      } else { // done
        pq.push(mp(curr.first + edge.first, mp(edge.second, 3)));
      }
    }
  }
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 34096 KB Output is correct
2 Correct 565 ms 28212 KB Output is correct
3 Correct 707 ms 35104 KB Output is correct
4 Correct 687 ms 33444 KB Output is correct
5 Correct 598 ms 29040 KB Output is correct
6 Correct 664 ms 34376 KB Output is correct
7 Correct 456 ms 25376 KB Output is correct
8 Correct 471 ms 25688 KB Output is correct
9 Correct 523 ms 27688 KB Output is correct
10 Incorrect 565 ms 34232 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 25708 KB Output is correct
2 Correct 579 ms 28916 KB Output is correct
3 Correct 504 ms 25432 KB Output is correct
4 Correct 437 ms 24592 KB Output is correct
5 Correct 619 ms 28580 KB Output is correct
6 Correct 720 ms 34604 KB Output is correct
7 Correct 500 ms 24224 KB Output is correct
8 Correct 645 ms 33296 KB Output is correct
9 Correct 499 ms 27444 KB Output is correct
10 Correct 419 ms 25320 KB Output is correct
11 Correct 214 ms 18716 KB Output is correct
12 Correct 700 ms 34972 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2692 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 63 ms 4896 KB Output is correct
5 Correct 33 ms 3276 KB Output is correct
6 Correct 3 ms 360 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 584 KB Output is correct
9 Correct 2 ms 480 KB Output is correct
10 Correct 43 ms 4544 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 34096 KB Output is correct
2 Correct 565 ms 28212 KB Output is correct
3 Correct 707 ms 35104 KB Output is correct
4 Correct 687 ms 33444 KB Output is correct
5 Correct 598 ms 29040 KB Output is correct
6 Correct 664 ms 34376 KB Output is correct
7 Correct 456 ms 25376 KB Output is correct
8 Correct 471 ms 25688 KB Output is correct
9 Correct 523 ms 27688 KB Output is correct
10 Incorrect 565 ms 34232 KB Output isn't correct
11 Halted 0 ms 0 KB -