Submission #720721

#	Time	Username	Problem	Language	Result	Execution time	Memory
720721		NeroZein	Event Hopping (BOI22_events)	C++17	10 / 100	1580 ms	177208 KiB

events

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

const int Log = 18; 
const int N = 5003;

int dis[N][N];
int l[N], r[N];
vector<int> g[N]; 

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];
  }
  auto intersect = [&](int x, int i, int j) {
    return x >= i && x <= j;
  };
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (intersect(r[i], l[j], r[j])) {
        g[i].push_back(j); 
      }
    }
  }  
  memset(dis, -1, sizeof dis); 
  auto Bfs = [&](int src) {
    queue<int> que;
    que.push(src); 
    dis[src][src] = 0;
    while (!que.empty()) {
      int v = que.front();
      que.pop(); 
      for (int u : g[v]) {
        if (dis[src][u] == -1) {
          dis[src][u] = dis[src][v] + 1;
          que.push(u); 
        }
      }
    }
  }; 
  for (int i = 1; i <= n; ++i) {
    Bfs(i);
    // cout << "v : " << i << '\n';
    // for (int j = 1; j <= n; ++j) {
    //   cout << dis[i][j] << ' ';
    // }
    // cout << '\n';
  }
  while (q--) {
    int u, v;
    cin >> u >> v;
    if (dis[u][v] == -1) {
      cout << "impossible" << '\n';
    } else {
      cout << dis[u][v] << '\n';
    }
  }
  return 0;
}

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