//#pragma GCC optimize("O1")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define forn(i,n) for (int i=0; i<n; ++i)
#define pb(x) push_back(x);
#define f first
#define s second
struct DSU {
vector<int> p;
vector<int> r;
DSU(int n) {
p.assign(n,0);
r.assign(n,0);
forn(i,n) p[i]=i;
}
int get(int i) {
return p[i]==i ? i : get(p[i]);
}
void uni(int a, int b) {
a=get(a);
b=get(b);
if (a==b) return;
if (r[a]==r[b]) r[a]++;
if (r[a]>r[b]) {
p[b]=a;
} else {
p[a]=b;
}
}
};
void dfs(vector<vector<int>>&adj, int u, vector<int>&d) {
for (auto v:adj[u]) {
d[v]=d[u]+1;
dfs(adj,v,d);
}
}
void solve() {
int n, m; cin>>n>>m;
vector<pair<int,int>> a(n);
vector<vector<int>> adj(n), rev(n);
DSU paiu(n);
map<int,int> was;
map<int,int> ind;
forn(i,n) {
int l,r; cin>>l>>r;
if (was[r]) {
paiu.uni(ind[r],i);
if (l<was[r]) {
was[r]=l;
ind[r]=i;
}
} else {
was[r]=l;
ind[r]=i;
}
}
set<pair<int,int>> s;
vector<int> in(n,0);
for (auto x:was) s.insert({x.f,ind[x.f]});
auto p = s.end(); --p;
for (;;--p) {
auto x=*p; int i=x.s;
auto it = s.upper_bound({was[x.f],-1});
auto z=*it; if (z.f<was[x.f]) ++it;
while (it!=s.end() && (*it).f<=x.f) {
if ((*it).s!=i) { adj[(*it).s].pb(i); in[i]++; rev[i].pb((*it).s); }
++it;
}
if (p==s.begin()) break;
}
vector<vector<int>> jump(n,vector<int>(32,0));
vector<int> depth(n,0);
queue<int> q;
for (auto it:ind) if (in[it.s]==0) q.push(it.s); int root;
while (!q.empty()) {
int u=q.front(); q.pop();
if (adj[u].size()) {
jump[u][0]=adj[u][0];
} else {
jump[u][0]=u; root=u;
}
}
dfs(rev,root,depth);
for (int j=1; j<32; ++j) {
forn(i,n) {
jump[i][j]=jump[jump[i][j-1]][j-1];
}
}
forn(i,m) {
int u,v; cin>>u>>v;
--u,--v;
if (u==v) cout<<"0\n";
else if (depth[v]>depth[u]) cout<<"impossible\n";
else {
int ans=0;
for (int i=31; i>=0; --i) {
if (depth[jump[u][i]]<=depth[v]) continue;
cout<<u<<"->"<<jump[u][i]<<" 2^"<<i<<'\n';
u=jump[u][i];
ans+=(1<<i);
}
if (jump[u][0]==v) cout<<ans+1<<'\n';
else cout<<"impossible\n";
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
Compilation message
events.cpp: In function 'void solve()':
events.cpp:97:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
97 | for (auto it:ind) if (in[it.s]==0) q.push(it.s); int root;
| ^~~
events.cpp:97:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
97 | for (auto it:ind) if (in[it.s]==0) q.push(it.s); int root;
| ^~~
events.cpp:107:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
107 | dfs(rev,root,depth);
| ~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
252 ms |
89840 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
