oj.uz

Submission #1086328

# Submission time Handle Problem Language Result Execution time Memory
1086328 2024-09-10T07:50:48 Z pemguimn Passport (JOI23_passport) C++14
48 / 100
 24 ms 31400 KB 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5 + 5, NODE = 8e5 + 5, INF = 2e9 + 7;

int n, q, l[N], r[N], ans[N], idn[N];

vector<array<int, 2>> adj[N];

void build(int id = 1, int l = 1, int r = n){
    if(l == r){
        idn[l] = id; return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid), build(id * 2 + 1, mid + 1, r);
    adj[id * 2].push_back({id, 0}), adj[id * 2 + 1].push_back({id, 0});
}

void add(int id, int tl, int tr, int l, int r, int p){
    if(r < tl || tr < l) return;
    if(l <= tl && tr <= r) {
        adj[id].push_back({idn[p], 1});
        return;
    }
    int mid = (tl + tr) / 2;
    add(id * 2, tl, mid, l, r, p), add(id * 2 + 1, mid + 1, tr, l, r, p);
}

void dijkstra(vector<int> &d){
    priority_queue<array<int, 2>> pq;
    for(int i = 1; i <= 4 * n; i++){
        if(d[i] < 1e9) pq.push({-d[i], i});
    }

    while(!pq.empty()){
        auto [c, i] = pq.top(); pq.pop();
        c = -c;
        if(c != d[i]) continue;
        for(auto [x, w] : adj[i]){
            if(d[x] > d[i] + w){
                d[x] = d[i] + w;
                pq.push({-d[x], x});
            }
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
        add(1, 1, n, l[i], r[i], i);
    }


    vector<int> d1(4 * n + 1, INF); d1[idn[1]] = 0; dijkstra(d1);
    vector<int> d2(4 * n + 1, INF); d2[idn[n]] = 0; dijkstra(d2);
    vector<int> d3(4 * n + 1, INF);
    d1[idn[1]] = 1, d2[idn[n]] = 1;
    for(int i = 1; i <= n; i++){
        int x = idn[i];
        d3[x] = min(d3[x], d1[x] + d2[x] - 1);
    }
    dijkstra(d3);
    cin >> q;
    while(q--){
        int x; cin >> x;
        int ans = d3[idn[x]];
        if(ans >= 1e9) cout << -1;
        else cout << ans;
        cout << '\n';
    }
    return 0;
}

Compilation message

passport.cpp: In function 'void dijkstra(std::vector<long long int>&)':
passport.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         auto [c, i] = pq.top(); pq.pop();
      |              ^
passport.cpp:41:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for(auto [x, w] : adj[i]){
      |                  ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Runtime error 24 ms 31400 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5164 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5164 KB Output is correct
16 Correct 6 ms 5976 KB Output is correct
17 Correct 5 ms 5932 KB Output is correct
18 Correct 5 ms 6232 KB Output is correct
19 Correct 6 ms 6232 KB Output is correct
20 Correct 4 ms 5724 KB Output is correct
21 Correct 4 ms 5724 KB Output is correct
22 Correct 3 ms 5724 KB Output is correct
23 Correct 6 ms 5980 KB Output is correct
24 Correct 5 ms 6232 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5164 KB Output is correct
16 Correct 6 ms 5976 KB Output is correct
17 Correct 5 ms 5932 KB Output is correct
18 Correct 5 ms 6232 KB Output is correct
19 Correct 6 ms 6232 KB Output is correct
20 Correct 4 ms 5724 KB Output is correct
21 Correct 4 ms 5724 KB Output is correct
22 Correct 3 ms 5724 KB Output is correct
23 Correct 6 ms 5980 KB Output is correct
24 Correct 5 ms 6232 KB Output is correct
25 Correct 2 ms 4952 KB Output is correct
26 Correct 2 ms 4956 KB Output is correct
27 Correct 6 ms 6196 KB Output is correct
28 Correct 4 ms 5980 KB Output is correct
29 Correct 4 ms 5712 KB Output is correct
30 Correct 4 ms 5724 KB Output is correct
31 Correct 7 ms 5824 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Runtime error 24 ms 31400 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -