oj.uz

Submission #1086689

# Submission time Handle Problem Language Result Execution time Memory
1086689 2024-09-11T09:19:37 Z daoquanglinh2007 Passport (JOI23_passport) C++17
6 / 100
 423 ms 78128 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2e5, inf = 1e9+7;

int N, Q, L[NM+5], R[NM+5];
vector <pii> adj[4*NM+5];
int dist[2][4*NM+5];
deque <int> dq;
priority_queue <pii, vector <pii>, greater <pii> > pq;
int res[4*NM+5];

void update(int id, int l, int r, int u, int v, int x){
    if (v < l || u > r) return;
    if (l >= u && r <= v){
        if (l == r){
            adj[l].push_back(mp(x, 1));
        }
        else{
            adj[N+id].push_back(mp(x, 1));
        }
        return;
    }
    int mid = (l+r)/2;
    update(2*id, l, mid, u, v, x);
    update(2*id+1, mid+1, r, u, v, x);
}

void solve(int id, int l, int r){
    if (l == r) return;
    int mid = (l+r)/2;
    solve(2*id, l, mid);
    solve(2*id+1, mid+1, r);
    adj[(l < mid ? N+2*id : l)].push_back(mp(N+id, 0));
    adj[(mid+1 < r ? N+2*id+1 : r)].push_back(mp(N+id, 0));
}

void binary_bfs(int s, int dist[NM+5]){
    for (int i = 1; i <= 4*N; i++) dist[i] = +inf;
    dist[s] = 0;
    dq.push_back(s);
    while (!dq.empty()){
        int u = dq.front();
        dq.pop_front();
        for (pii p : adj[u]){
            int v = p.fi, w = p.se;
            if (dist[u]+w >= dist[v]) continue;
            dist[v] = dist[u]+w;
            if (w == 0) dq.push_front(v);
            else dq.push_back(v);
        }
    }
}

void dijkstra(){
    for (int i = 1; i <= 4*N; i++){
        res[i] = min(dist[0][i]+dist[1][i], +inf);
        pq.push(mp(res[i], i));
    }
    while (!pq.empty()){
        int u = pq.top().se;
        if (res[u] != pq.top().fi){
            pq.pop();
            continue;
        }
        pq.pop();
        for (pii p : adj[u]){
            int v = p.fi, w = p.se;
            if (res[u]+w >= res[v]) continue;
            res[v] = res[u]+w;
            pq.push(mp(res[v], v));
        }
    }
}

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

    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> L[i] >> R[i];
        update(1, 1, N, L[i], R[i], i);
    }
    solve(1, 1, N);
    binary_bfs(1, dist[0]);
    binary_bfs(N, dist[1]);
    dijkstra();
    cin >> Q;
    while (Q--){
        int X; cin >> X;
        if (res[X] == +inf) cout << -1; else cout << res[X];
        cout << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 8 ms 19032 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 423 ms 78128 KB Output is correct
5 Correct 261 ms 58380 KB Output is correct
6 Correct 190 ms 53444 KB Output is correct
7 Correct 163 ms 55228 KB Output is correct
8 Correct 122 ms 59616 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 8 ms 19264 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Incorrect 8 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 8 ms 19264 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Incorrect 8 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19036 KB Output is correct
2 Correct 8 ms 19036 KB Output is correct
3 Correct 8 ms 19264 KB Output is correct
4 Correct 7 ms 19036 KB Output is correct
5 Correct 8 ms 19032 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Incorrect 8 ms 19036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19036 KB Output is correct
2 Correct 8 ms 19032 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 423 ms 78128 KB Output is correct
5 Correct 261 ms 58380 KB Output is correct
6 Correct 190 ms 53444 KB Output is correct
7 Correct 163 ms 55228 KB Output is correct
8 Correct 122 ms 59616 KB Output is correct
9 Correct 12 ms 19036 KB Output is correct
10 Correct 8 ms 19036 KB Output is correct
11 Correct 8 ms 19264 KB Output is correct
12 Correct 7 ms 19036 KB Output is correct
13 Correct 8 ms 19032 KB Output is correct
14 Correct 9 ms 19036 KB Output is correct
15 Correct 9 ms 19036 KB Output is correct
16 Incorrect 8 ms 19036 KB Output isn't correct
17 Halted 0 ms 0 KB -