제출 #730408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730408		tch1cherin	Railway Trip 2 (JOI22_ho_t4)	C++17	52 / 100	2047 ms	39552 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));
      }
    }
  }
  if (K == N - 1) {
    vector<vector<int>> nxt(N, vector<int>(20)), lst(N, vector<int>(20));
    for (int i = 0; i < N; i++) {
      lst[i][0] = L[i];
      nxt[i][0] = R[i];
    }
    for (int i = 0; i < N; i++) {
      for (int j = 0; j + 1 < 20; j++) {
        lst[i][j + 1] = lst[lst[i][j]][j];
      }
    }
    for (int i = N - 1; i >= 0; i--) {
      for (int j = 0; j + 1 < 20; j++) {
        nxt[i][j + 1] = nxt[nxt[i][j]][j];
      }
    }
    int Q;
    cin >> Q;
    while (Q--) {
      int S, T;
      cin >> S >> T;
      S--, T--;
      int ans = 0;
      if (S < T) {
        for (int i = 20 - 1; i >= 0; i--) {
          if (nxt[S][i] < T) {
            ans += (1 << i);
            S = nxt[S][i];
          }
        }
      } else {
        for (int i = 20 - 1; i >= 0; i--) {
          if (lst[S][i] > T) {
            ans += (1 << i);
            S = lst[S][i];
          }
        }
      }
      cout << (ans == (1 << 20) - 1 ? -1 : ans + 1) << "\n";
    }
    return;
  }
  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: 25 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13