#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;
bool cmp(vector<int> a, vector<int> b) {
return a[1] < b[1];
}
vector<vector<int>> g;
int curc = 0;
vector<int> col;
vector<int> par;
vector<vector<int>> ups;
vector<int> dist;
void dfs(int v, int di = 0, int p = -1) {
col[v] = curc;
dist[v] = di;
par[v] = v;
if (p != -1)
par[v] = p;
for (auto u : g[v]) {
if (u != p) {
dfs(u, di + 1,v);
}
}
}
int logn;
int lca(int v, int u) {
if (dist[u] > dist[v]) {
swap(v, u);
}
for (int i = logn - 1; i>= 0; i--) {
if (dist[ups[i][v]] >= dist[u])
v = ups[i][v];
}
for (int i = logn - 1; i >= 0; i--) {
if (ups[i][v] != ups[i][u]) {
v = ups[i][v];
u = ups[i][u];
}
}
if (v == u)
return v;
return par[v];
}
int n;
int dijkstra(int s, int e) {
dist.assign(n, inf);
dist[s] = 0;
set<pair<int, int>> st = {{0, s}};
while(!st.empty()) {
auto pa = *st.begin();
st.erase(pa);
int v = pa.se;
int d = pa.fi;
for(auto u : g[v]) {
if (dist[u] > d + 1) {
st.erase({dist[u], u});
dist[u] = d + 1;
st.insert({dist[u], u});
}
}
}
return dist[e];
}
bool check(vector<vector<int>> s) {
sort(s.begin(), s.end());
bool ok = 1;
for (int i = 0; i < s.size() - 1; i++) {
if (s[i][1] >= s[i + 1][1])
ok = 0;
}
return ok;
}
signed main() {
int q;
cin >> n >> q;
col.resize(n, -1);
par.resize(n);
dist.resize(n);
vector<pair<int, int>> evinit(n);
set<int> comst;
map<int, int> nval, inival;
for (int i = 0; i < n; i++) {
cin >> evinit[i].fi >> evinit[i].se;
comst.insert(evinit[i].fi);
comst.insert(evinit[i].se);
}
int cur = 0;
for (auto el : comst) {
nval[el] = cur;
inival[cur] = el;
cur++;
}
vector<vector<int>> eve(n, vector<int>(3));
for (int i = 0; i < n; i++) {
eve[i][0] = nval[evinit[i].fi];
eve[i][1] = nval[evinit[i].se];
eve[i][2] = i;
}
if (n <= 1000 && q <= 100) {
g.resize(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
if (eve[j][0] <= eve[i][1] && eve[i][1] <= eve[j][1]) {
g[i].push_back(j);
}
}
}
for (int qw = 0; qw < q; qw++) {
int s, e;
cin >> s >> e;
s--;
e--;
int val = dijkstra(s, e);
if (val == inf) {
cout << "impossible" << '\n';
} else {
cout << val << '\n';
}
}
return 0;
}
vector<int> nind(n);
vector<int> begs;
int type = 2;
if (check(eve)) {
type = 1;
sort(eve.begin(), eve.end());
for (int i = 0; i < n; i++) {
nind[eve[i][2]] = i;
}
g.resize(n);
for (int i = 0; i < n; i++) {
int val = eve[i][1];
int l = i, r = n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (eve[mid][0] <= val) {
l = mid;
} else {
r = mid;
}
}
if (l == i) {
begs.push_back(i);
} else {
g[i].push_back(l);
g[l].push_back(i);
}
}
} else {
sort(eve.begin(), eve.end(), cmp);
for (int i = 0; i < n; i++) {
nind[eve[i][2]] = i;
}
g.resize(n);
int p = n - 1;
int end = eve[n - 1][0];
begs.push_back(n - 1);
for (int i = n - 2; i >= 0; i--) {
if (eve[i][1] >= end) {
g[i].push_back(p);
g[p].push_back(i);
} else {
begs.push_back(i);
}
if (eve[i][0] <= end) {
p = i;
end = eve[i][0];
}
}
}
for (auto el : begs) {
if (col[el] == -1) {
dfs(el);
curc++;
}
}
logn = 1;
int vallog = 1;
while (vallog < n) {
vallog *= 2;
logn++;
}
logn+=3;
ups.resize(logn, vector<int>(n));
for (int i = 0; i < n; i++) {
ups[0][i] = par[i];
}
for (int j = 1; j < logn; j++) {
for (int i = 0; i < n; i++) {
ups[j][i] = ups[j - 1][ups[j - 1][i]];
}
}
for (int qw = 0; qw < q; qw++) {
int s, e;
cin >> s >> e;
s--;
e--;
s = nind[s];
e = nind[e];
if (col[s] != col[e]) {
cout << "impossible" << '\n';
} else {
if (type == 2) {
int lc = lca(s, e);
if (lc == e || (eve[e][1] == eve[lc][1])){
cout << dist[e] - dist[lc] + (dist[s] - dist[lc]) << '\n';
} else {
cout << "impossible" << '\n';
}
} else {
if (eve[e][0] < eve[s][0]) {
cout << "impossible" << '\n';
}
int v = s;
for (int i = logn - 1; i>= 0; i--) {
if (eve[ups[i][v]][0] < eve[e][0])
v = ups[i][v];
}
if (eve[v][0] < eve[e][0])
v = par[v];
cout << dist[s] - dist[v] << '\n';
}
}
}
}
# | 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... |