Submission #573095

#	Time	Username	Problem	Language	Result	Execution time	Memory
573095		StrawHatWess	Event Hopping (BOI22_events)	C++17	10 / 100	1600 ms	131560 KiB

events

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

typedef vector<int>vi; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF=2e9;
const int MX=1e5+10; 



void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////


int N,Q; 
vi L(MX), R(MX);  

vi adj[MX]; 

int main(){
	IO(); 

	cin>>N>>Q; 

	FOR(i,1,N+1) cin>>L[i]>>R[i]; 

	
	FOR(i,1,N+1) FOR(j,1,N+1) if(i!=j){
		if(R[i]>=L[j] && R[i]<=R[j]) adj[i].pb(j); 
	}


	vector<vi> dist(N+1, vi(N+1,INF)); 

	FOR(s,1,N+1){
		dist[s][s]=0; 

		queue<int>q; 
		q.push(s); 

		while(sz(q)){
			int u=q.front(); 
			q.pop(); 

			for(int v: adj[u]) if(dist[s][v]==INF){
				dist[s][v]=dist[s][u]+1; 
				q.push(v); 
			}
		}
	}	


	while(Q--){
		int s,e; cin>>s>>e; 

		if(dist[s][e]==INF) cout << "impossible" << endl;
		else cout << dist[s][e] << endl; 
	}
}

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