oj.uz

Submission #941523

# Submission time Handle Problem Language Result Execution time Memory
941523 2024-03-09T05:02:33 Z Gromp15 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 12184 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1564 ms 12184 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Incorrect 5 ms 1116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Incorrect 5 ms 1116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Incorrect 5 ms 1116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1544 ms 11620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1564 ms 12184 KB Time limit exceeded
3 Halted 0 ms 0 KB -