Submission #646022

#TimeUsernameProblemLanguageResultExecution timeMemory
646022GaLzEvent Hopping (BOI22_events)C++14
10 / 100
1582 ms130732 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; const ll mod=1e9+7; const ll maxn=1e5+5; const int INF=1e8; #define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fi first #define se second #define pb push_back #define ub upper_bound #define lb lower_bound #define endl '\n' vi adj[maxn]; int n, q, dis[5001][5001], u, v; pii arr[maxn]; int main() { ok cin >> n >> q; for(int i=1; i<=n; i++) cin >> arr[i].fi >> arr[i].se; if(n<=5000) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i==j) continue; if(arr[i].se>=arr[j].fi && arr[i].se<=arr[j].se) adj[i].pb(j); } } memset(dis, -1, sizeof dis); for(int i=1; i<=n; i++) { dis[i][i]=0; queue<int> qu; qu.push(i); while(!qu.empty()) { int fr=qu.front(); qu.pop(); for(auto it : adj[fr]) { if(dis[i][it]==-1) { dis[i][it]=dis[i][fr]+1; qu.push(it); } } } } while(q--) { cin >> u >> v; if(dis[u][v]==-1) cout << "impossible"; else cout << dis[u][v]; cout << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...