Submission #1109033

#TimeUsernameProblemLanguageResultExecution timeMemory
1109033n3rm1nEvent Hopping (BOI22_events)C++17
0 / 100
3 ms1104 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 ans[MAXN]; int start, dist[MAXN], used[MAXN]; void bfs() { for (int i = 1; i <= n; ++ i) { dist[i] = 1e9; } 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); } } } void sort_queries() { for (int i = 1; i <= q; ++ i) { int from, to; cin >> from >> to; que[from].push_back(make_pair(to, i)); } } int main() { speed(); read_events(); make_edges(); sort_queries(); for (int i = 1; i <= n; ++ i) { if(!que[i].size())continue; start = i; bfs(); for (auto &[v, qi]: que[i]) { ans[qi] = dist[v]; } } for (int i = 1; i <= q; ++ i) { assert(ans[i] <= 1e9); assert(ans[i] >= 0); if(ans[i] == 1e9)cout << "impossible" << endl; else cout << ans[i] << 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...