This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N, Q;
vector<ll> S, E;
vector<array<ll, 3>> ranges;
vector<vector<ll>> dist;
void solve(){
cin>>N>>Q;
S.assign(N, 0);
E.assign(N, 0);
ranges.assign(N, array<ll, 3>());
dist.assign(N, vector<ll>(N, INT_MAX));
// graph.assign(N, vector<int>());
for(int i = 0; i < N; i++){
int s, e;
cin>>s>>e;
S[i] = s;
E[i] = e;
ranges[i] = {s, e, i};
}
sort(ranges.begin(), ranges.end(), [&](array<ll, 3> a, array<ll, 3> b){
return a[1] > b[1];
});
for(int q = 0; q < Q; q++){
int sq, eq;
cin>>sq>>eq;
sq--;
eq--;
queue<int> que;
que.push(sq);
dist[sq][sq] = 0;
while(!que.empty()){
int curr = que.front();
que.pop();
// vector<int> adj = graph[curr];
// cerco il primo nodo tale che end di quel nodo è < se
// posso trovarlo in O(logn)
int node = -1;
for(int j = 0; j < N; j++){
if(dist[sq][ranges[j][2]] == INT_MAX && ranges[j][0] <= E[curr] && ranges[j][1] >= E[curr] && ranges[j][1] <= E[eq]) {
node = ranges[j][2];
if(node != -1){
dist[sq][node] = dist[sq][curr] +1;
que.push(node);
}
}
}
/*
for(int a : adj){
if(dist[sq][a] != INT_MAX) continue;
dist[sq][a] = dist[sq][curr]+1;
que.push(a);
}
*/
}
if(dist[sq][eq] == INT_MAX)
cout<<"impossible"<<endl;
else cout<<dist[sq][eq]<<endl;
}
}
int main(){
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |