Submission #1111147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111147		mispertion	Passport (JOI23_passport)	C++17	100 / 100	622 ms	101148 KiB

passport

#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 = 2e5 + 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], q, cur, ru, lc[4 * N], rc[4 * N], a[4 * N], b[4 * N], d[4 * N];
vector<pair<int, int>> g[4 * 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;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46