Submission #790480

#	Time	Username	Problem	Language	Result	Execution time	Memory
790480		Johann	Passport (JOI23_passport)	C++14	100 / 100	569 ms	47124 KiB

passport

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
pii operator+(const pii &a, const pii &b) { return {a.first + b.first, a.second + b.second}; }
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int INF = 1 << 30;
int N, Q;
vpii R;
vi Qu;
vvi dp;
vi toL, toR, toBoth, ans; // distance

struct segtree
{
    int size;
    vvi arr;
    void init(int _size)
    {
        size = 1;
        while (size < _size)
            size *= 2;
        arr.assign(2 * size, vi());
    }
    void add(int l, int r, int i) { add(l, r, i, 1, 0, size); }
    void add(int l, int r, int i, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            arr[x].push_back(i);
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        add(l, r, i, 2 * x, lx, m);
        add(l, r, i, 2 * x + 1, m, rx);
    }
    void query(int i, vi &neigh)
    {
        i += size;
        while (i > 0)
        {
            while (!arr[i].empty())
                neigh.push_back(arr[i].back()), arr[i].pop_back();
            i >>= 1;
        }
    }
};

segtree seg;

void djikstra(priority_queue<pii, vpii, greater<pii>> &q, vi &dist)
{
    seg.init(N);
    for (int i = 0; i < N; ++i)
        seg.add(R[i].first, R[i].second, i);

    vb vis(N, 0);
    vi neigh;
    while (!q.empty())
    {
        int d, v;
        tie(d, v) = q.top(), q.pop();

        if (vis[v])
            continue;

        dist[v] = d;
        vis[v] = true;
        seg.query(v, neigh);
        for (int u : neigh)
        {
            if (dist[u] <= d + 1)
                continue;
            dist[u] = d + 1;
            q.push({d + 1, u});
        }
        neigh.clear();
    }
}

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

    cin >> N;
    R.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> R[i].first >> R[i].second, --R[i].first;
    seg.init(N);

    cin >> Q;
    Qu.resize(Q);
    for (int i = 0; i < Q; ++i)
        cin >> Qu[i], --Qu[i];

    priority_queue<pii, vpii, greater<pii>> q;
    for (int i = 0; i < N; ++i)
        if (R[i].first == 0)
            q.push({1, i});
    toL.assign(N, INF);
    djikstra(q, toL);
    assert(q.empty());

    for (int i = 0; i < N; ++i)
        if (R[i].second == N)
            q.push({1, i});
    toR.assign(N, INF);
    djikstra(q, toR);
    assert(q.empty());

    toBoth.assign(N, INF);
    for (int i = 0; i < N; ++i)
        if (toL[i] != INF && toR[i] != INF)
        {
            toBoth[i] = toL[i] + toR[i] - 1;
            q.push({toBoth[i], i});
        }
    ans.assign(N, INF);
    djikstra(q, ans);

    for (int x : Qu)
        if (ans[x] == INF)
            cout << -1 << "\n";
        else
            cout << ans[x] << "\n";

    return 0;
}

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