제출 #842207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842207		d4xn	Event Hopping (BOI22_events)	C++17	10 / 100	1587 ms	22740 KiB

events

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

const int N = 1e5;

int n, q;
pair<int, int> sg[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    sg[i] = make_pair(l, r);
  }

  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;

    int z = -1;
    vector<bool> vis(n, 0);
    queue<pair<int, int>> qu;
    qu.push(make_pair(0, x));
    while (!qu.empty()) {
      int d = qu.front().first;
      int u = qu.front().second;
      qu.pop();

      if (vis[u]) continue;
      vis[u] = 1;

      if (u == y) {
        z = d;
        break;
      }

      for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        if (sg[i].first <= sg[u].second && sg[u].second <= sg[i].second) {
          qu.push(make_pair(d+1, i));
        }
      }
    }

    if (z == -1) cout << "impossible\n";
    else cout << z << "\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