Submission #1173075

#TimeUsernameProblemLanguageResultExecution timeMemory
1173075domblyEvent Hopping (BOI22_events)C++20
10 / 100
1597 ms43668 KiB
#include <bits/stdc++.h> #define F first #define S second using namespace std; const int N = 5000 + 10; int Dist[N][N], n, l[N], r[N]; vector<int> g[N]; void Bfs(int s) { for(int i = 1; i <= n; i++) Dist[s][i] = n + 1; queue<int> q; Dist[s][s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int j : g[u]) { if(Dist[s][j] > Dist[s][u] + 1) { Dist[s][j] = Dist[s][u] + 1; q.push(j); } } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int q; cin >> n >> q; for(int i = 1; i <= n; i++) cin >> l[i] >> r[i]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i != j && l[j] <= r[i] && r[j] >= r[i]) { //cout << i << " -> " << j << endl; g[i].push_back(j); } } } for(int i = 1; i <= n; i++) Bfs(i); while(q--) { int l, r; cin >> l >> r; if(Dist[l][r] == n + 1) { cout << "impossible\n"; } else { cout << Dist[l][r] << "\n"; } } }
#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...