Submission #1280017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280017		Icelast	Passport (JOI23_passport)	C++20	100 / 100	639 ms	127048 KiB

passport

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
vector<int> bfs01(int n, int s, vector<vector<pair<int, int>>> adj){
    vector<int> d(n+1, INF);
    deque<int> dq;
    d[s] = 0;
    dq.push_front(s);
    while(!dq.empty()){
        int u = dq.front();
        dq.pop_front();
        for(auto it : adj[u]){
            int v = it.first, w = it.second;
            if(d[u] + w < d[v]){
                d[v] = d[u] + w;
                if(w == 0){
                    dq.push_front(v);
                }else{
                    dq.push_back(v);
                }
            }
        }
    }
    return d;
}
vector<int> dijkstra(int n, vector<int> dist, vector<vector<pair<int, int>>> &adj){
    vector<bool> vis(n+1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 1; i <= n; i++){
        if(dist[i] != INF){
            pq.push({dist[i], i});
        }
    }
    while(!pq.empty()){
        int d_u = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(vis[u]){
            continue;
        }
        vis[u] = true;
        for(auto it : adj[u]){
            int v = it.first;
            int w = it.second;
            if(vis[v]) continue;
            if(dist[v] > d_u+w){
                dist[v] = d_u+w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
void solve(){
    int n;
    cin >> n;
    vector<int> l(n+1), r(n+1);
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
    }
    int N = 1;
    while(N < n) N*=2;
    int M = N*2-1;
    auto get = [&](int l, int r) -> vector<int>{
        vector<int> res;
        auto dfs = [&](auto dfs, int u, int low, int high) -> void{
            if(low > r || l > high) return;
            if(low >= l && r >= high){
                res.push_back(u);
                return;
            }
            int mid = (low+high)/2;
            dfs(dfs, u*2, low, mid);
            dfs(dfs, u*2+1, mid+1, high);
        };
        dfs(dfs, 1, 1, N);
        return res;
    };
    vector<vector<pair<int, int>>> adj_rev(M+1);
    auto add_edge = [&](int u, int v, int w) -> void{
        adj_rev[v].push_back({u, w});
    };
    auto dfs = [&](auto dfs, int u, int low, int high) -> void{
        if(low == high) return;
        int mid = (low+high)/2;
        add_edge(u, u*2, 0);
        add_edge(u, u*2+1, 0);
        dfs(dfs, u*2, low, mid);
        dfs(dfs, u*2+1, mid+1, high);
    };
    dfs(dfs, 1, 1, N);
    for(int i = 1; i <= n; i++){
        for(int j : get(l[i], r[i])){
            add_edge(i+N-1, j, 1);
        }
    }
    vector<int> a = bfs01(M, 1+N-1, adj_rev), b = bfs01(M, n+N-1, adj_rev);
    vector<int> dab(M+1, INF);
    for(int i = 1; i <= n; i++){
        dab[i+N-1] = a[i+N-1] + b[i+N-1];
        if(i != 1 && i != n){
            dab[i+N-1]--;
        }
    }
    vector<int> d = dijkstra(M, dab, adj_rev);
    for(int i = 1; i <= n; i++){
        int j = i+N-1;
        if(d[j] > n){
            d[j] = -1;
        }
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++){
        int x;
        cin >> x;
        cout << d[x+N-1] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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