제출 #889879

#제출 시각아이디문제언어결과실행 시간메모리
889879shivensinha4Passport (JOI23_passport)C++17
48 / 100
2155 ms907608 KiB
#include "bits/stdc++.h" #ifdef mlocal #include "./Competitive-Code-Library/snippets/prettyprint.h" #endif using namespace std; #define for_(i, s, e) for (int i = s; i < (int) e; i++) #define for__(i, s, e) for (ll i = s; i < e; i++) typedef long long ll; typedef vector<int> vi; typedef array<int, 2> ii; #define endl '\n' const int INF = 1e9, BS = 400; int main() { #ifdef mlocal freopen("test.in", "r", stdin); #endif ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; const int blocks = (n + BS - 1) / BS; vector<ii> seg(n); vector<vi> can_reach(n), can_reach_b(blocks); for_(i, 0, n){ cin >> seg[i][0] >> seg[i][1], seg[i][0]--, seg[i][1]--; int pt = seg[i][0]; while (pt % BS != 0 and pt <= seg[i][1]) { can_reach[pt].push_back(i); pt++; } while (pt + BS <= seg[i][1]) { can_reach_b[pt / BS].push_back(i); pt += BS; } while (pt <= seg[i][1]) { can_reach[pt].push_back(i); pt++; } } function<vi(int)> bfs = [&] (int s) { vi dist(n, INF); auto cr = can_reach, crb = can_reach_b; dist[s] = 0; queue<int> q; q.push(s); while (q.size()) { auto p = q.front(); q.pop(); for (auto i: cr[p]) if (dist[i] == INF) { dist[i] = dist[p] + 1; q.push(i); } for (auto i: crb[p / BS]) { if (dist[i] == INF) { dist[i] = dist[p] + 1; q.push(i); } } crb[p / BS].clear(); } return dist; }; vi ans = bfs(0); { vi ans2 = bfs(n - 1); for_(i, 0, n) ans[i] += ans2[i]; } for_(i, 1, n - 1) if (ans[i] < INF) ans[i]--; priority_queue<ii, vector<ii>, greater<ii>> pq; for_(i, 0, n) pq.push({ans[i], i}); while (pq.size()) { auto [dist, p] = pq.top(); pq.pop(); if (dist != ans[p]) continue; for (auto i: can_reach[p]) { if (ans[i] > ans[p] + 1) { ans[i] = ans[p] + 1; pq.push({ans[i], i}); } } for (auto i: can_reach_b[p / BS]) { if (ans[i] > ans[p] + 1) { ans[i] = ans[p] + 1; pq.push({ans[i], i}); } } can_reach_b[p / BS].clear(); } int q; cin >> q; while (q--) { int p; cin >> p; p--; cout << (ans[p] >= INF ? -1 : ans[p]) << 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...