Submission #1109035

#TimeUsernameProblemLanguageResultExecution timeMemory
1109035n3rm1nEvent Hopping (BOI22_events)C++17
10 / 100
1584 ms30844 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN = 5e3 + 10; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int n, q, s[MAXN], e[MAXN]; void read_events() { cin >> n >> q; for (int i = 1; i <= n; ++ i) cin >> s[i] >> e[i]; } vector < int > g[MAXN]; void make_edges() { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { if(i == j)continue; if(s[j] <= e[i] && e[i] <= e[j]) g[i].push_back(j); } } } vector < pair < int, int > > que[MAXN]; int start, dist[MAXN], used[MAXN]; void bfs() { for (int i = 1; i <= n; ++ i) { dist[i] = 1e9; used[i] = 0; } queue < int > q; q.push(start); used[start] = 1; dist[start] = 0; while(!q.empty()) { int beg = q.front(); q.pop(); for (auto nb: g[beg]) { if(used[nb])continue; dist[nb] = dist[beg] + 1; used[nb] = 1; q.push(nb); } } } int main() { speed(); read_events(); make_edges(); for (int i = 1; i <= q; ++ i) { int from, to; cin >> from >> to; start = from; bfs(); if(dist[to] == 1e9)cout << "impossible" << endl; else cout << dist[to] << endl; } return 0; }
#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...