Submission #1229398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229398		avighna	Event Hopping (BOI22_events)	C++20	10 / 100	1595 ms	1804 KiB

events

#include <bits/stdc++.h>

int main() {
  int n, q;
  std::cin >> n >> q;
  struct time {
    int s, e;
  };
  std::vector<time> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i].s >> a[i].e;
  }

  const int inf = 1e9;

  while (q--) {
    int beg, end;
    std::cin >> beg >> end;
    --beg, --end;
    std::queue<int> q;
    std::vector<int> ans(n, inf);
    ans[beg] = 0;
    q.push(beg);
    while (!q.empty()) {
      int u = q.front();
      if (u == end) {
        break;
      }
      q.pop();
      for (int i = 0; i < n; ++i) {
        if (a[i].s <= a[u].e and a[u].e <= a[i].e and ans[u] + 1 < ans[i]) {
          ans[i] = ans[u] + 1;
          q.push(i);
        }
      }
    }
    if (ans[end] == inf) {
      std::cout << "impossible\n";
    } else {
      std::cout << ans[end] << '\n';
    }
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30