oj.uz

Submission #798383

# Submission time Handle Problem Language Result Execution time Memory
798383 2023-07-30T16:24:51 Z vjudge1 Passport (JOI23_passport) C++17
0 / 100
 27 ms 5924 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;
const int M = (1 << 3);
vector<pair<int, int>> g[3 * M];

void build(int l = 0, int r = M - 1, int v = 1) {
    if(l == r) {
        g[l].push_back({v + M, 0});
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * v);
    build(mid + 1, r, 2 * v + 1);
    g[2 * v + M].push_back({v + M, 0});
    g[2 * v + M + 1].push_back({v + M, 0});
}

void add(int ql, int qr, int u, int l = 0, int r = M - 1, int v = 1) {
    if(qr < l || ql > r) 
        return;
    if(ql <= l && r <= qr) {
        g[v + M].push_back({u, 1});
        return;
    }
    int mid = (l + r) / 2;
    add(ql, qr, u, l, mid, 2 * v);
    add(ql, qr, u, mid + 1, r, 2 * v + 1); 
}

int n;
vector<ll> dijkstra(vector<pair<int, ll>> start) {
    vector<ll> dist(3 * M, INF + 10);
    for(auto [i, d] : start) dist[i] = d;
    set<pair<ll, int>> st;
    for(int i = 0; i < (int)dist.size(); i++) 
        st.insert({dist[i], i});
    while(!st.empty()) {
        int s = st.begin()->second;
        st.erase(st.begin());
        for(auto [to, w] : g[s]) {
            if(dist[to] > dist[s] + w) {
                st.erase({dist[to], to});
                dist[to] = dist[s] + w;
                st.insert({dist[to], to});
            }
        }
    }
    vector<ll> res(n + 1);
    for(int i = 1; i <= n; i++)
        res[i] = dist[i];
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    build();
    cin >> n;
    int l[n + 1], r[n + 1];
    for(int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        add(l[i], r[i], i);
    }
    auto A = dijkstra({{1, 0}});
    auto B = dijkstra({{n, 0}});
    // for(int i = 1; i <= n; i++) 
    //     cout << A[i] << ' ';
    // cout << '\n';
    // for(int i = 1; i <= n; i++) 
    //     cout << B[i] << ' ';
    // cout << '\n';
    vector<pair<int, ll>> C;
    for(int i = 1; i <= n; i++) 
        C.push_back({i, A[i] + B[i] - (1 < i && i < n)});
    auto F = dijkstra(C);
    // for(int i = 1; i <= n; i++) 
    //     cout << F[i] << ' ';
    // cout << '\n';

    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        if(F[x] >= INF) cout << -1 << '\n';
        else cout << F[x] << '\n';
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Runtime error 27 ms 5924 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 8.0

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

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Runtime error 27 ms 5924 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -