Submission #1211054

#TimeUsernameProblemLanguageResultExecution timeMemory
1211054jerzykPassport (JOI23_passport)C++20
100 / 100
495 ms92712 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1'000'000'000'000'000'000LL; const int II = 1'000'000'000; const ll M = 1'000'000'007LL; const int N = 1<<18; vector<pair<int, int>> ed[3 * N]; pair<int, int> ran[N]; int dis[3 * N], vis[3 * N], d2[3 * N]; pair<int, int> que[3 * N]; queue<int> q[2]; int answer[3 * N]; int Get() { int a; if((int)q[0].size() > 0 && ((int)q[1].size() == 0 || dis[q[0].front()] <= dis[q[1].front()])) {a = q[0].front(); q[0].pop();} else {a = q[1].front(); q[1].pop();} return a; } void BFS(int s, int n) { int v; for(int i = 1; i <= n; ++i) {dis[i] = II; vis[i] = 0;} dis[s] = 0; q[0].push(s); while((int)(q[0].size() + q[1].size()) > 0) { v = Get(); if(vis[v]) continue; vis[v] = 1; for(int i = 0; i < (int)ed[v].size(); ++i) { if(dis[ed[v][i].st] > dis[v] + ed[v][i].nd) { dis[ed[v][i].st] = dis[v] + ed[v][i].nd; q[ed[v][i].nd].push(ed[v][i].st); } } } } void BFSA(int n) { int v, j = 0; for(int i = 1; i <= n; ++i) { vis[i] = 0; dis[i] = min(dis[i], II); que[i] = pair{dis[i], i}; } sort(que + 1, que + 1 + n); while(j < n || (int)(q[0].size() + q[1].size()) > 0) { if((int)(q[0].size() + q[1].size()) == 0) { ++j; q[0].push(que[j].nd); } v = Get(); while(j < n && que[j + 1].st <= dis[v]) { ++j; q[0].push(que[j].nd); } if(vis[v]) continue; vis[v] = 1; for(int i = 0; i < (int)ed[v].size(); ++i) { if(dis[ed[v][i].st] > dis[v] + ed[v][i].nd) { dis[ed[v][i].st] = dis[v] + ed[v][i].nd; q[ed[v][i].nd].push(ed[v][i].st); } } } } void Add(int a, int b, int v) { a += N - 1; b += N + 1; while(a / 2 != b / 2) { if(a % 2 == 0) ed[a + 1].pb(make_pair(v, 1)); if(b % 2 == 1) ed[b - 1].pb(make_pair(v, 1)); a /= 2; b /= 2; } } int Mi(int a, int b) { a += N - 1; b += N + 1; int m1 = II, m2 = II; while(a / 2 != b / 2) { if(a % 2 == 0) {m1 = min(m1, dis[a + 1]); m2 = min(m2, d2[a + 1]);} if(b % 2 == 1) {m1 = min(m1, dis[b - 1]); m2 = min(m2, d2[b - 1]);} a /= 2; b /= 2; } return min(II, m1 + m2); } void Solve() { int n, m, q, a, b; cin >> n; m = 2 * N - 1; for(int i = 1; i <= n; ++i) { cin >> a >> b; ran[i] = pair{a, b}; Add(a, b, i + N); } BFS(N + 1, m); for(int i = 1; i <= m; ++i) d2[i] = dis[i]; BFS(N + n, m); for(int i = 1; i <= m; ++i) answer[i] = d2[i] + dis[i]; for(int i = 1; i <= n; ++i) answer[i + N] = min(answer[i + N], Mi(ran[i].st, ran[i].nd) + 1); for(int i = 1; i <= m; ++i) dis[i] = answer[i]; BFSA(m); for(int i = 1; i <= n; ++i) { answer[i] = dis[i + N]; if(answer[i] >= II) answer[i] = -1; } cin >> q; for(int i = 1; i <= q; ++i) { cin >> a; cout << answer[a] << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //int t; cin >> t; //while(t--) for(int i = 2; i < 2 * N; ++i) ed[i].pb(pair{i / 2, 0}); Solve(); 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...