Submission #1170948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170948		JuanJL	Event Hopping (BOI22_events)	C++20	0 / 100	160 ms	6812 KiB

events

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

struct E{
	ll s;
	ll e;
	E(ll s=0,ll e=0): s(s), e(e) {}
};

bool operator<(const E &a, const E &b){
	if(a.s<b.s) return true;
	if(a.s>b.s) return false;
	return a.e<b.e;
}

const int MAXN = 100000+5;

ll n,q;
vector<pair<E,ll>> eventS;
vector<E> event;

ll lvl[MAXN];
ll   p[MAXN];


void dfs(ll nd, ll lv , ll pa){

	//	cout<<nd<<'\n';

	lvl[nd]=lv;
	p[nd]=pa;

	ll ind = lower_bound(ALL(eventS),(pair<E,ll>){E(event[nd].s,event[nd].e),0})-eventS.begin();
	if(eventS[ind].snd==nd) ind++;
	if(ind<SZ(eventS)){
	ind = eventS[ind].snd;
	
	if(event[ind].s<=event[nd].e){
		dfs(ind,lv+1,pa);
	}
	}
}



int main(){

	cin >> n >> q;
	
	event.clear();
	event.resize(n);
	eventS.clear();
	eventS.resize(n);
	
	forn(i,0,n){
		cin >> event[i].s >> event[i].e;
	}
	
	forn(i,0,n){
		eventS[i].fst=event[i];
		eventS[i].snd=i;
	}
	
	sort(ALL(eventS));

	//cout<<"llega\n";
	forn(i,0,n) p[i]=-1;
	
	forn(i,0,n) if(p[eventS[i].snd]==-1){
		dfs(eventS[i].snd,0,eventS[i].snd);
	}
	//cout<<"pasa\n";
	ll a,b;
	forn(i,0,q){
		cin>>a>>b; a--; b--;
		if(p[a]!=p[b]||lvl[a]>lvl[b]){
			cout<<"impossible\n";
		}else{
			cout<<lvl[b]-lvl[a]<<'\n';
		}
	}
	return 0;
}

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