Submission #878676

#	Time	Username	Problem	Language	Result	Execution time	Memory
878676		thangdz2k7	Passport (JOI23_passport)	C++17	0 / 100	6 ms	23388 KiB

passport

#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
#define pb push_back

using namespace std;

const int N = 2e5 + 5;

int n, pos[N];
vector <ii> adj[4 * N];
int dist[3][4 * N];
int mx = 0, used[4 * N];

void build(int s, int l, int r){
    used[s] = false;
    for (int i = 0; i <= 2; ++ i) dist[i][s] = 1e9;
    mx = max(mx, s);
    if (l == r){
        if (l != 1 and l != n) used[s] = true;
        pos[l] = s;
        return;
    }

    int mid = l + r >> 1;
    build(2 * s, l, mid);
    build(2 * s + 1, mid + 1, r);
    adj[2 * s].pb(ii(s, 0));
    adj[2 * s + 1].pb(ii(s, 0));
}

void get(int s, int l, int r, int u, int v, int pos){
    if (u <= l and r <= v) {
        adj[s].pb(ii(pos, 1));
        return;
    }
    int mid = l + r >> 1;
    if (mid >= u) get(2 * s, l, mid, u, v, pos);
    if (mid + 1 <= v) get(2 * s + 1, mid + 1, r, u, v, pos);
}

priority_queue <ii> pq;

void dijktra(int curdist[]){
    while (!pq.empty()){
        int u = pq.top().S;
        int du = -pq.top().F;
        pq.pop();
        if (du != curdist[u]) continue;
        for (ii v : adj[u]){
            if (curdist[v.F] > du + v.S){
                curdist[v.F] = du + v.S;
                pq.push(ii(-curdist[v.F], v.F));
            }
        }
    }
}

void solve(){
    cin >> n;
    build(1, 1, n);
    for (int i = 1; i <= n; ++ i){
        int l, r; cin >> l >> r;
        get(1, 1, n, l, r, pos[i]);
    }
    dist[0][pos[1]] = 0;
    pq.push(ii(0, pos[1]));
    dijktra(dist[0]);

    dist[1][pos[n]] = 0;
    pq.push(ii(0, pos[n]));
    dijktra(dist[1]);

    //cout << endl;

    for (int i = 1; i <= mx; ++ i) {
        //cout << dist[0][i] << ' ' << dist[1][i] << endl;
        if (used[i] == true) dist[2][i] = dist[0][i] + dist[1][i] - 1;
        //cout << dist[2][i] << endl;
        pq.push(ii(-dist[2][i], i));
        dijktra(dist[2]);
    }


    int q; cin >> q;
    while (q --){
        int x; cin >> x;
        if (dist[2][pos[x]] >= 1e9) cout << -1 << '\n';
        else cout << dist[2][pos[x]] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void build(int, int, int)':
passport.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void get(int, int, int, int, int, int)':
passport.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~

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