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 <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define all(x) x.begin(), x.end()
#define len(s) (int) s.size()
#define md ((l + r) >> 1)
#define pb push_back
#define S second
#define F first
// #define int long long
using namespace std;
typedef int ll;
typedef long double ld;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 5e3 + 11;
const int MAX = (1 << 16);
const int mod = 998244353;
const long long inf = 1e9 + 10;
const double eps = 1e-9;
ll n, q;
ll l[N], r[N], d[N][N];
bool was[N];
vector < ll > g[N];
void bfs(ll s){
queue < ll > q;
fill(was, was + N, 0);
d[s][s] = 0, was[s] = 1;
q.push(s);
while(!q.empty()){
ll v = q.front();
q.pop();
for(ll u : g[v])
if(!was[u])
d[s][u] = d[s][v] + 1, q.push(u), was[u] = 1;
}
}
void output(){
cin >> n >> q;
for(ll i = 0; i < N; i++)
for(ll j = 0; j < N; j++)
d[i][j] = -1;
for(ll i = 1; i <= n; i++) cin >> l[i] >> r[i];
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= n; j++){
if(l[j] <= r[i] && r[i] <= r[j]){
g[i].pb(j);
}
}
}
for(ll i = 1; i <= n; i++){
bfs(i);
}
while(q--){
ll s, f;
cin >> s >> f;
if(d[s][f] == -1) cout << "impossible\n";
else cout << d[s][f] << '\n';
}
}
const bool cases = 0;
signed main(){
// file("disrupt");
adiyer();
int tt = 1;
if(cases) cin >> tt;
for(int i = 1; i <= tt; i++){
output();
}
}
# | 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... |