제출 #1229392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229392		avighna	Event Hopping (BOI22_events)	C++20	0 / 100	835 ms	48876 KiB

events

#include <bits/stdc++.h>

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

  auto comp = [](time a, time b) {
    if (a.e != b.e) {
      return a.e < b.e;
    }
    return a.s < b.s;
  };
  std::sort(a.begin(), a.end(), comp);
  std::vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    p[a[i].i] = i;
  }
  std::map<int, std::vector<int>> events_at;
  for (int i = 0; i < n; ++i) {
    auto [s, e, i_orig] = a[i];
    for (auto it = st.lower_bound(s); it != st.end() and *it <= e; ++it) {
      events_at[*it].push_back(i);
    }
  }

  int tot_comps = 0, timer = 0;
  std::vector<int> comp_num(n), start(n);
  std::vector<bool> vis(n);
  auto dfs = [&](auto &&self, int u) {
    if (vis[u]) {
      return;
    }
    vis[u] = true;
    start[u] = timer++;
    comp_num[u] = tot_comps;
    for (auto &i : events_at[a[u].e]) {
      if (i == u) {
        continue;
      }
      self(self, i);
    }
  };
  for (int i = 0; i < n; ++i) {
    dfs(dfs, i);
    tot_comps++;
  }

  while (q--) {
    int beg, end;
    std::cin >> beg >> end;
    --beg, --end;
    beg = p[beg], end = p[end];
    if (a[beg].s == a[end].s and a[beg].e == a[end].e) {
      std::cout << (beg != end) << '\n';
    } else if (comp_num[beg] != comp_num[end] or start[beg] > start[end]) {
      std::cout << "impossible\n";
    } else {
      std::cout << start[end] - start[beg] << '\n';
    }
  }
}

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