Submission #735158

#	Time	Username	Problem	Language	Result	Execution time	Memory
735158		four_specks	Passport (JOI23_passport)	C++17	100 / 100	962 ms	89444 KiB

passport

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

void solve()
{
    int n;
    cin >> n;

    int m = 1 << __lg(2 * n - 1);

    vector<vector<pair<int, int>>> adj(2 * m + n);
    for (int i = 1; i < m; i++)
    {
        adj[2 * i].emplace_back(i, 0);
        adj[2 * i + 1].emplace_back(i, 0);
    }

    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r, --l;

        adj[2 * m + i].emplace_back(i + m, 1);

        for (l += m, r += m; l < r; l /= 2, r /= 2)
        {
            if (l % 2 == 1)
                adj[l++].emplace_back(2 * m + i, 0);
            if (r % 2 == 1)
                adj[--r].emplace_back(2 * m + i, 0);
        }
    }

    auto dijkstra = [&](vector<int> &dist) -> void
    {
        priority_queue<pair<int, int>> pq;
        for (int i = 1; i < 2 * m + n; i++)
        {
            if (dist[i] != 2 * n)
                pq.emplace(-dist[i], i);
        }

        while (!pq.empty())
        {
            auto [d, u] = pq.top();
            pq.pop();

            if (-d != dist[u])
                continue;

            for (auto [v, wt] : adj[u])
            {
                if (dist[u] + wt < dist[v])
                {
                    dist[v] = dist[u] + wt;
                    pq.emplace(-dist[v], v);
                }
            }
        }
    };

    vector f(2 * m + n, 2 * n), g(2 * m + n, 2 * n), h(2 * m + n, 2 * n);

    g[m] = h[m + n - 1] = 0;

    dijkstra(g);
    dijkstra(h);

    for (int i = 1; i < 2 * m + n; i++)
    {
        if (max(g[i], h[i]) != 2 * n)
            f[i] = g[i] + h[i];
    }

    dijkstra(f);

    int q;
    cin >> q;

    for (int i = 0; i < q; i++)
    {
        int j;
        cin >> j, --j;

        cout << (f[j + m] != 2 * n ? f[j + m] : -1) << '\n';
    }
}

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

    solve();

    return 0;
}

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