Submission #940769

#	Time	Username	Problem	Language	Result	Execution time	Memory
940769		alextodoran	Passport (JOI23_passport)	C++17	100 / 100	511 ms	94500 KiB

passport

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int INF = INT_MAX / 2;

int N;
int L[N_MAX + 2], R[N_MAX + 2];
int Q;

vector <pair <int, int>> adj[N_MAX * 4 + 2];

int encode[N_MAX * 4 + 2];
void build (int node, int l, int r) {
    if (l == r) {
        encode[node] = l;
        return;
    }
    encode[node] = node + N;
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    build(left, l, mid);
    build(right, mid + 1, r);
    adj[encode[left]].push_back({encode[node], 0});
    adj[encode[right]].push_back({encode[node], 0});
}
void build () {
    build(1, 1, N);
}
void connect_range (int node, int l, int r, int i) {
    if (L[i] <= l && r <= R[i]) {
        adj[encode[node]].push_back({i, 1});
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    if (L[i] <= mid) {
        connect_range(left, l, mid, i);
    }
    if (mid + 1 <= R[i]) {
        connect_range(right, mid + 1, r, i);
    }
}
void connect_range (int i) {
    connect_range(1, 1, N, i);
}

int dp_left[N_MAX * 4 + 2];
int dp_right[N_MAX * 4 + 2];
int dp_full[N_MAX * 4 + 2];

vector <int> at_dist[N_MAX + 2];
bool seen[N_MAX * 4 + 2];

void Dijkstra (int dist[]) {
    for (int i = 1; i <= N; i++) {
        if (dist[i] < N) {
            at_dist[dist[i]].push_back(i);
        }
    }
    fill(dist + N + 1, dist + N * 4 + 1, INF);
    fill(seen + 1, seen + N * 4 + 1, false);
    for (int d = 0; d < N; d++) {
        while (at_dist[d].empty() == false) {
            int u = at_dist[d].back();
            at_dist[d].pop_back();
            if (seen[u] == true) {
                continue;
            }
            seen[u] = true;
            for (pair <int, int> e : adj[u]) {
                int v, c; tie(v, c) = e;
                if (dist[u] + c < dist[v]) {
                    dist[v] = dist[u] + c;
                    if (dist[v] < N) {
                        at_dist[dist[v]].push_back(v);
                    }
                }
            }
        }
    }
}

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

    cin >> N;
    build();
    for (int i = 1; i <= N; i++) {
        cin >> L[i] >> R[i];
        connect_range(i);
        dp_left[i] = (L[i] == 1 ? 0 : INF);
        dp_right[i] = (R[i] == N ? 0 : INF);
    }
    Dijkstra(dp_left);
    Dijkstra(dp_right);
    for (int i = 1; i <= N; i++) {
        dp_full[i] = min(INF, dp_left[i] + dp_right[i]);
    }
    Dijkstra(dp_full);
    cin >> Q;
    while (Q--) {
        int i;
        cin >> i;
        cout << (dp_full[i] != INF ? dp_full[i] + 1 : -1) << "\n";
    }

    return 0;
}

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