Submission #721701

#	Time	Username	Problem	Language	Result	Execution time	Memory
721701		Mardonbekhazratov	Event Hopping (BOI22_events)	C++17	0 / 100	1564 ms	2228 KiB

events

#include<bits/stdc++.h>
#define ff first
#define sd second
using namespace std;
const int INF=1e9+1;
bool cmp(pair<int,int>a,pair<int,int>b){return (a.ff<b.ff);}
int main(){
	int n,q;cin>>n>>q;
	vector<pair<int,int> >a(n);
	for(int i=0;i<n;i++) cin>>a[i].ff>>a[i].sd;
	while(q--){
		int s,d;cin>>s>>d;--s,--d;
		vector<pair<int,int> > b;
		int l=a[s].ff,r=a[d].sd;
		for(int i=0;i<n;i++){
			if(a[i].sd<=r&&a[i].sd>=a[s].sd) b.push_back(a[i]);
		}
		sort(b.begin(),b.end(),cmp);
		int N=b.size();
		vector<int>dp(N,INF);
		for(int i=0;i<N;i++) if(b[i].ff==l&&b[i].sd==a[s].sd) dp[i]=0;
		if(b.size()==0){
			cout<<"impossible";
			continue;
		}
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(b[i].ff<=b[j].sd&&b[i].sd>b[j].sd) dp[i]=min(dp[i],dp[j]+1);
			}
		}
		for(int i=0;i<n;i++){
			if(b[i].ff==a[d].ff&&b[i].sd==r) {if(dp[i]==INF) cout<<"impossible";else cout<<dp[i];cout<<'\n';break;}
		}
	}
}

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