Submission #1253621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253621		NHristov	Passport (JOI23_passport)	C++20	100 / 100	521 ms	76168 KiB

passport

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 2e5 + 5;

int n;
int ord;

vector < pair < int, int > > g[4 * N];
int leftChild[4 * N], rightChild[4 * N];

int build(int l, int r)
{
    if (l == r)
    {
        return l;
    }

    int mid = (l + r) / 2;

    int node = ++ord;
    int L = build(l, mid), R = build(mid + 1, r);

    leftChild[node] = L, rightChild[node] = R;

    g[L].push_back({node, 0});
    g[R].push_back({node, 0});

    return node;
}

void update(int node, int l, int r, int ql, int qr, int num)
{
    if (l > qr || r < ql)
    {
        return;
    }

    if (ql <= l && r <= qr)
    {
        g[node].push_back({num, 1});

        return;
    }

    int mid = (l + r) / 2;

    if (ql <= mid)
    {
        update(leftChild[node], l, mid, ql, qr, num);
    }

    if (mid + 1 <= qr)
    {
        update(rightChild[node], mid + 1, r, ql, qr, num);
    }
}

int dist[4 * N][2];

void bfs01(int type, int st)
{
    for (int i = 1; i <= ord; i++)
    {
        dist[i][type] = -1;
    }

    deque < int > dq;

    dist[st][type] = 0;
    dq.push_back(st);

    while (!dq.empty())
    {
        int u = dq.front();

        dq.pop_front();

        for (auto [v, w] : g[u])
        {
            if (dist[v][type] != -1)
            {
                continue;
            }

            dist[v][type] = dist[u][type] + w;

            if (w == 0)
            {
                dq.push_front(v);
            }
            else
            {
                dq.push_back(v);
            }
        }
    }
}

int ans[4 * N];

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

    cin >> n;

    ord = n;

    int root = build(1, n);

    for (int i = 1; i <= ord; i++)
    {
        ans[i] = -1;
    }

    for (int i = 1; i <= n; i++)
    {
        int l, r;

        cin >> l >> r;

        update(root, 1, n, l, r, i);
    }

    bfs01(0, 1);
    bfs01(1, n);

    priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > pq;

    for (int i = 1; i <= n; i++)
    {
        if (dist[i][0] != -1 && dist[i][1] != -1)
        {
            ans[i] = max(1, dist[i][0]) + max(1, dist[i][1]) - 1;
            pq.push({ans[i], i});
        }
    }

    while (!pq.empty())
    {
        int u = pq.top().second;

        pq.pop();

        for (auto [v, w] : g[u])
        {
            if (ans[v] == -1 || ans[v] > ans[u] + w)
            {
                ans[v] = ans[u] + w;
                pq.push({ans[v], v});
            }
        }
    }

    int t;

    cin >> t;

    while (t--)
    {
        int query;

        cin >> query;

        cout << ans[query] << endl;
    }

    return 0;
}

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