oj.uz

Submission #721701

# Submission time Handle Problem Language Result Execution time Memory
721701 2023-04-11T06:39:16 Z Mardonbekhazratov Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 2228 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 2228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -