Submission #1218373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218373		teslerpham	Passport (JOI23_passport)	C++20	100 / 100	1074 ms	197572 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define el '\n'

using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vll = vector<ll>;

const int INF = 1e9 + 7;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;

void fastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
struct Edge{
    int u, v, w;
};
int n, dist[3][N + (N << 2)];
vector<int>g[N + (N << 2)];
vector<Edge> E;

void addEdge(int u, int v, int w){
    g[u].pb(sz(E));
    E.pb(Edge(u,v,w));
}
void build(int id, int l, int r){
    if(l == r){
        addEdge(l, id + n, 0);
        return;
    }
    int mid = (l + r)/2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    addEdge(id * 2 + n, id + n, 0);
    addEdge(id * 2 + n + 1, id + n, 0);
}
void update(int id, int l, int r, int u, int v, int x){
    if(l >= u && r <= v){
        addEdge(id + n, x, 1);
        return;
    }
    int mid = (l + r)/2;
    if(u <= mid) update(id * 2, l, mid, u, v, x);
    if(v > mid) update(id * 2 + 1, mid + 1, r, u, v, x);

}

void bfs_01(int id, int source){
    for(int i = 1; i <= n + (n << 2); i++){
        dist[id][i] = 1e9;
    }
    dist[id][source] = 0;
    deque<int> q;
    q.push_front(source);
    while(!q.empty()){
        int x = q.front();
        q.pop_front();
        for(int ide : g[x]){
            int v = E[ide].u ^ E[ide].v ^ x; //Tìm đỉnh còn lại của cạnh E[ide] ngoài đỉnh x
            if(dist[id][v] > dist[id][x] + E[ide].w){
                dist[id][v] = dist[id][x] + E[ide].w;
                if(!E[ide].w)q.push_front(v);
                else q.pb(v);
            }
        }
    }
}
signed main() {
    fastIO();

    cin >> n;
    for(int i = 1; i <= n; i++){
        int l, r; cin >> l >> r;
        update(1, 1, n, l, r, i);
    }
    build(1, 1, n);
    bfs_01(0, 1);
    bfs_01(1, n);
    priority_queue<pii> pq;
    for(int i = 1; i <= n + (n << 2); i++)dist[2][i] = 1e9;
    for(int i = 1; i <= n; i++){
        if(max(dist[0][i], dist[1][i]) < 1e9){ 
            dist[2][i] = dist[0][i] + dist[1][i] - (i != 1 && i != n); // L[i] <= i <= R[i] so it's easy here
            pq.push({-dist[2][i], i});
        }
    }

    while(!pq.empty()){
        pair<int,int> eq = pq.top(); pq.pop();

        int x = eq.se;
        if(-eq.fi > dist[2][x]) continue;

        for(int ide : g[x]){
            int v = E[ide].u ^ E[ide].v ^ x;

            if(dist[2][v] > dist[2][x] + E[ide].w){
                dist[2][v] = dist[2][x] + E[ide].w;
                pq.push({-dist[2][v], v});
            }
        }
    }

    int q; cin >> q;
    while(q--){
        int u; cin >> u;

        cout << (dist[2][u] == 1e9 ? -1 : dist[2][u]) << "\n";
    }
    return 0;
}

/*
⢀⡴⠑⡄⠀⠀⠀⠀⠀⠀⠀⣀⣀⣤⣤⣤⣀⡀      Monkey D. LUFFY
⠸⡇⠀⠿⡀⠀⣀⡴⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀   "I’m gonna be..."
⠀⠀⠀⠀⠑⢄⣾⣷⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣯⣍⠻⣷⡄   ...King of the Pirates!
⠀⠀⠀⠀⢀⡀⠁⠈⠙⠻⠿⠿⠿⠿⠿⠿⠿⠿⠿⠿⠿⠟⠋   ⠀
⠀⠀⠀⢀⡾⣁⣀⠀⠴⠂⠙⣗⡀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⣴⣷⠘⠿⠛⠃⠀⠀⠀⠉⠳⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣴⣿⠙⣆⠀⠀⠀⠀⠀⠀⠀⠈⠙⠒⠊⠁⠀⠀⠀⠀⠀
⢀⣼⣿⠀⣇⣀⠀⠀⣠⣤⣶⣾⣿⣶⣶⣶⣶⠆⠀⠀⠀⠀

*/

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