Submission #1128350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128350		m_bezrutchka	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	477 ms	35560 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> pii;
typedef pair<int, pii> pip;
typedef pair<pii, int> ppi;
typedef pair<pii, pii> ppp;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const int LLINF = 2e18 + 10;

const int MAXN = 2e5 + 10;

int n;
vector<pii> adj[MAXN];

vector<int> dijkstra(int s) {
  priority_queue<pii> pq;
  vector<int> dist(n + 1, LLINF);
  vector<int> mrk(n + 1, false);
  pq.push({-0, s});
  dist[s] = 0;
  while (!pq.empty()) {
    int v = pq.top().second;
    pq.pop();
    if (mrk[v]) continue;
    mrk[v] = true;
    for (auto [w, c]: adj[v]) {
      if (!mrk[w] && dist[w] > dist[v] + c) {
        dist[w] = dist[v] + c;
        pq.push({-dist[w], w});
      }
    }
  }
  return dist;
}

int commuter_pass(int bu, int bv, int s, int t, vector<int> &dh, vector<int> &ds) {
  priority_queue<pip> pq;
  // 0 -- nao entrou; 1 -- dentro; 2 -- ja saiu
  vector<vector<int>> dist(3);
  vector<vector<bool>> mrk(3);
  for (int i = 0; i < 3; i++) {
    dist[i].clear(); mrk[i].clear();
    for (int j = 0; j <= n; j++) {
      dist[i].push_back(LLINF);
      mrk[i].push_back(false);
    }
  }
  // cerr << "done initializing" << endl;
  dist[0][bu] = 0;
  if (dh[bu] + ds[bu] == dh[t]) {
    dist[1][bu] = 0;
    pq.push({-0, {1, bu}});  
  }
  dist[2][bu] = 0;
  pq.push({-0, {0, bu}});
  pq.push({-0, {2, bu}});

  while (!pq.empty()) {
    int k = pq.top().second.first;
    int v = pq.top().second.second;
    pq.pop();
    if (mrk[k][v]) continue;
    mrk[k][v] = true;

    bool v_in_pass = (dh[v] + ds[v] == dh[t]);

    for (auto [w, c]: adj[v]) {
      // caso em que nao uso commuter pass nessa aresta
      if (!mrk[k][w] && dist[k][w] > dist[k][v] + c) {
        dist[k][w] = dist[k][v] + c;
        pq.push({-dist[k][w], {k, w}});
      }

      bool w_in_pass = (dh[w] + ds[w] == dh[t]);
      // cerr << "checking if " << w << " is in path: " << w_in_pass << endl;

      // entrando no commuter pass agora
      if (k == 0 && w_in_pass) {
        if (!mrk[1][w] && dist[1][w] > dist[0][v] + c) {
          dist[1][w] = dist[0][v] + c;
          pq.push({-dist[1][w], {1, w}});
        }
      }

      // dentro do commuter pass
      if (k == 1) {
        // saindo agora
        if (!mrk[2][w] && dist[2][w] > dist[1][v] + c) {
          dist[2][w] = dist[1][v] + c;
          pq.push({-dist[2][w], {2, w}});
        }

        bool same_path = (dh[v] + ds[w] + c == dh[t] || dh[w] + ds[v] + c == dh[t]);
        // cerr << "checking if " << v << " and " << w << " on same path: " << same_path << endl;

        // free ride!
        if (v_in_pass && w_in_pass && same_path) {
          if (!mrk[1][w] && dist[1][w] > dist[1][v]) {
            dist[1][w] = dist[1][v];
            pq.push({-dist[1][w], {1, w}});
          }
        }
      }
    }
  }
  // for (int k = 0; k < 3; k++) {
  //   cout << "STEP " << k << endl;
  //   for (int i = 1; i <= n; i++) {
  //     cout << "dist[" << i << "] = " << dist[k][i] << endl;
  //   }
  // }
  return min({ dist[0][bv], dist[1][bv], dist[2][bv] });
}

void solve() {
  int m, house, school, book_u, book_v;
  cin >> n >> m >> house >> school >> book_u >> book_v;
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  cerr << "hello world" << endl;
  vector<int> d_house = dijkstra(house);
  cerr << "done first dijkstra" << endl;
  vector<int> d_school = dijkstra(school);
  cerr << "done second dijkstra" << endl;
  cout << commuter_pass(book_u, book_v, house, school, d_house, d_school) << endl;
}

int32_t main() {
  solve();
  return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45