Submission #941523

#	Time	Username	Problem	Language	Result	Execution time	Memory
941523		Gromp15	Event Hopping (BOI22_events)	C++17	0 / 100	1564 ms	12184 KiB

events

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
	int n, q;
	cin >> n >> q;
	vector<ar<int, 2>> a(n);
	vector<ar<int, 3>> events;
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1];
		events.push_back({a[i][0], 0, i});
		events.push_back({a[i][1], 1, i});
	}
	sort(all(events));
	vector<vector<int>> adj(n);
	set<int> got;
	for (auto [time, tp, idx] : events) {
		if (tp == 0) got.insert(idx);
		else {
			for (int x : got) {
				adj[idx].push_back(x);
			}
			got.erase(idx);
		}
	}
	while (q--) {
		int x, y; cin >> x >> y, x--, y--;
		vector<int> dist(n, 1e9);
		dist[x] = 0;
		queue<int> q;
		q.push(x);
		while (q.size()) {
			int v = q.front(); q.pop();
			for (int u : adj[v]) if (ckmin(dist[u], dist[v] + 1)) q.push(u);
		}
		if (dist[y] == 1e9) cout << "impossible\n";
		else cout << dist[y] << '\n';
	}

}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

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