Submission #595421

#	Time	Username	Problem	Language	Result	Execution time	Memory
595421		Hacv16	Event Hopping (BOI22_events)	C++17	10 / 100	1593 ms	77416 KiB

events

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

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cout << #x << ": " << "[ " << x << " ]\n"

int n, q, h[MAX];
vector<int> adj[MAX];

struct event{
	int s, e;
} ev[MAX];

bool f(event a, event b){ //can i do a --> b ?
	return b.s <= a.e && a.e <= b.e;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    cin >> n >> q;
    
    for(int i = 1; i <= n; i++){
    	cin >> ev[i].s >> ev[i].e;
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			
			if(f(ev[i], ev[j])) adj[i].pb(j);
		}
	}
	
	while(q--){
		int s, e; cin >> s >> e;
		
		queue<int> q;
		vector<int> dist(n + 1, -1);
		
		q.push(s); dist[s] = 0;
		
		while(q.size()){
			int u = q.front();
			q.pop();
			
			for(auto v : adj[u]){
				if(dist[v] == -1){
					dist[v] = dist[u] + 1;
					q.push(v);
				}
			}
		}
		
		if(dist[e] == -1) cout << "impossible" << '\n';
		else cout << dist[e] << '\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