제출 #730401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730401		tch1cherin	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2040 ms	21824 KiB

Main

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

struct Event {
  int modl, modr, type;

  Event() {}

  Event(int _modl, int _modr, int _type) : modl(_modl), modr(_modr), type(_type) {}
};

void solve() {
  int N, K;
  cin >> N >> K;
  int M;
  cin >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    A[i]--, B[i]--;
  }
  vector<vector<Event>> events(N);
  for (int i = 0; i < M; i++) {
    if (A[i] < B[i]) {
      events[A[i]].emplace_back(N, B[i], 1);
      events[min(A[i] + K - 1, B[i])].emplace_back(N, B[i], -1);
    } else {
      events[max(A[i] - K + 1, B[i])].emplace_back(B[i], -1, 1);
      events[A[i]].emplace_back(B[i], -1, -1);
    }
  }
  vector<int> L(N), R(N);
  multiset<int> sl, sr;
  for (int i = 0; i < N; i++) {
    L[i] = i, R[i] = i;
    for (auto [modl, modr, type] : events[i]) {
      if (type == 1) {
        sl.insert(modl);
        sr.insert(modr);
      }
    }
    if (!sl.empty()) {
      L[i] = min(L[i], *sl.begin());
      R[i] = max(R[i], *sr.rbegin());
    }
    for (auto [modl, modr, type] : events[i]) {
      if (type == -1) {
        sl.erase(sl.find(modl));
        sr.erase(sr.find(modr));
      }
    }
  }
  int Q;
  cin >> Q;
  while (Q--) {
    int S, T;
    cin >> S >> T;
    S--, T--;
    queue<int> q;
    set<int> unvisited;
    for (int i = 0; i < N; i++) {
      if (i != S) {
        unvisited.insert(i);
      }
    }
    vector<int> dist(N, N);
    dist[S] = 0;
    q.push(S);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      auto it = unvisited.lower_bound(L[u]);
      while (it != unvisited.end() && *it <= R[u]) {
        dist[*it] = dist[u] + 1;
        q.push(*it);
        it = next(it);
        unvisited.erase(prev(it));
      }
    }
    cout << (dist[T] == N ? -1 : dist[T]) << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13