Submission #1000388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000388		pcc	Event Hopping (BOI22_events)	C++17	10 / 100	71 ms	4572 KiB

events

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1010;
pii arr[mxn];
vector<int> paths[mxn];
int N,Q;
int dist[mxn];
queue<int> q;

void BFS(int s){
	fill(dist,dist+mxn,mxn);
	q.push(s);
	dist[s] = 0;
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		for(auto nxt:paths[now]){
			if(dist[nxt]>dist[now]+1)dist[nxt] = dist[now]+1,q.push(nxt);
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++){
		cin>>arr[i].fs>>arr[i].sc;
	}
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=N;j++){
			if(i == j)continue;
			if(arr[i].fs<=arr[j].sc&&arr[j].sc<=arr[i].sc)paths[j].push_back(i);
		}
	}
	while(Q--){
		int s,t;
		cin>>s>>t;
		BFS(s);
		if(dist[t]>=mxn)cout<<"impossible\n";
		else cout<<dist[t]<<'\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