Submission #701327

#	Time	Username	Problem	Language	Result	Execution time	Memory
701327		angelo_torres	Event Hopping (BOI22_events)	C++17	10 / 100	1572 ms	32836 KiB

events

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int n,q,s[N],e[N],d[N];
bool o[N];
vector<int> g[N];

void bfs(int v){
	for(int i = 1; i <= n; ++i) d[i] = N, o[i] = 0;
	d[v] = 0;
	queue<int> q;
	q.push(v);
	while(!q.empty()){
		int r = q.front();
		q.pop();
		for(auto u : g[r]){
			if(!o[u]){
				o[u] = 1, d[u] = d[r]+1;
				q.push(u);
			} 
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) cin >> s[i] >> e[i];
	if(n <= 5000){
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= n; ++j){
				if(i == j) continue;
				if(s[j] <= e[i] && e[i] <= e[j]){
					// cout << i << " " << j << "\n";
					g[i].push_back(j);
				}
			}
		}
		while(q--){
			int w,z; cin >> w >> z;
			bfs(w);
			if(d[z] == N){
				cout << "impossible\n";
			}else{
				cout << d[z] << "\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