Submission #1111144

#TimeUsernameProblemLanguageResultExecution timeMemory
1111144mispertionPassport (JOI23_passport)C++17
48 / 100
117 ms86092 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); using ll = long long; using ld = long double; using pii = pair<int, int>; #define F first #define S second const ld PI = 3.1415926535; const int N = 5e5 + 10; const int M = 1e7 + 1; ll mod = 998244353; const int infi = 1e9; const ll infl = 1e16; const int P = 31; int mult(int a, int b) { return a * 1LL * b % mod; } int sum(int a, int b) { if (a + b < 0) return a + b + mod; if (a + b >= mod) return a + b - mod; return a + b; } ll binpow(ll a, ll n) { if (n == 0) return 1; if (n % 2 == 1) { return binpow(a, n - 1) * a % mod; } else { ll b = binpow(a, n / 2); return b * b % mod; } } int n, L[N], R[N], V[N], q, cur, ru, lc[N], rc[N], a[N], b[N], d[N]; vector<pair<int, int>> g[N]; void buildup(int v, int tl, int tr){ if(tl == tr){ g[tl].push_back({v, 1}); return; } int tm = (tl + tr) / 2; lc[v] = ++cur; rc[v] = ++cur; g[lc[v]].push_back({v, 0}); g[rc[v]].push_back({v, 0}); buildup(lc[v], tl, tm); buildup(rc[v], tm + 1, tr); } void addup(int v, int tl, int tr, int l, int r, int x){ if(tl > r || l > tr) return; if(l <= tl && tr <= r){ g[v].push_back({x, 0}); return; } int tm = (tl + tr) / 2; addup(lc[v], tl, tm, l, r, x); addup(rc[v], tm + 1, tr, l, r, x); } void solve() { cin >> n; for(int i = 1; i <= n; i++) cin >> L[i] >> R[i]; cur = n + 1; ru = cur; buildup(ru, 1, n); for(int i = 1; i <= cur; i++){ a[i] = infi; b[i] = infi; } for(int i = 1; i <= n; i++){ addup(ru, 1, n, L[i], R[i], i); } deque<int> dq; for(int i = 1; i <= n; i++){ if(L[i] == 1) dq.push_back(i), a[i] = 0; } while(!dq.empty()){ int v = dq.front(); dq.pop_front(); for(auto e : g[v]){ int u = e.F, w = e.S; if(a[u] == infi){ a[u] = a[v] + w; if(w == 0) dq.push_front(u); else dq.push_back(u); } } } for(int i = 1; i <= n; i++) if(R[i] == n) dq.push_back(i), b[i] = 0; while(!dq.empty()){ int v = dq.front(); dq.pop_front(); for(auto e : g[v]){ int u = e.F, w = e.S; if(b[u] == infi){ b[u] = b[v] + w; if(w == 0) dq.push_front(u); else dq.push_back(u); } } } int nw = ++cur; for(int i = 1; i <= n; i++){ g[nw].push_back({i, a[i] + b[i] + 1}); } for(int i = 1; i <= cur; i++) d[i] = infi; d[nw] = 0; set<pii> st; st.insert({1, nw}); while(!st.empty()){ int v = st.begin()->S; st.erase(st.begin()); for(auto e : g[v]){ int u = e.F, w = e.S; if(d[u] > d[v] + w){ st.erase({d[u], u}); d[u] = d[v] + w; st.insert({d[u], u}); } } } int q; cin >> q; while(q--){ int x; cin >> x; cout << (d[x] > n ? -1 : d[x]) << '\n'; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while (t--) { 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...