oj.uz

Submission #878665

# Submission time Handle Problem Language Result Execution time Memory
878665 2023-11-25T04:00:30 Z thangdz2k7 Passport (JOI23_passport) C++17
0 / 100
 5 ms 25088 KB 
#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;

void build(int s, int l, int r){
    for (int i = 0; i <= 2; ++ i) dist[i][s] = 1e9;
    mx = max(mx, 2 * s + 1);
    if (l == r){
        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]);

    for (int i = 1; i <= mx; ++ i) {
        dist[2][i] = dist[0][i] + dist[1][i];
        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';
        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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24932 KB Output is correct
2 Incorrect 5 ms 24924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24928 KB Output is correct
2 Incorrect 5 ms 25088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24928 KB Output is correct
2 Incorrect 5 ms 25088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24928 KB Output is correct
2 Incorrect 5 ms 25088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24932 KB Output is correct
2 Incorrect 5 ms 24924 KB Output isn't correct
3 Halted 0 ms 0 KB -