Submission #1211045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211045		jerzyk	Passport (JOI23_passport)	C++20	In queue	0 ms	0 KiB

passport

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 1'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<18;
vector<pair<int, int>> ed[3 * N];
pair<int, int> ran[N];
int dis[3 * N], vis[3 * N], d2[3 * N];
pair<int, int> que[3 * N];
queue<int> q[2];

int answer[3 * N];

int Get()
{
    int a;
    if((int)q[0].size() > 0 && ((int)q[1].size() == 0 || dis[q[0].front()] <= dis[q[1].front()]))
    {a = q[0].front(); q[0].pop();}
    else
    {a = q[1].front(); q[1].pop();}
    return a;
}

void BFS(int s, int n)
{
    int v;
    for(int i = 1; i <= n; ++i)
        {dis[i] = II; vis[i] = 0;}
    dis[s] = 0;
    q[0].push(s);
    while((int)(q[0].size() + q[1].size()) > 0)
    {
        v = Get();
        if(vis[v]) continue;
        vis[v] = 1;
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(dis[ed[v][i].st] > dis[v] + ed[v][i].nd)
            {
                dis[ed[v][i].st] = dis[v] + ed[v][i].nd;
                q[ed[v][i].nd].push(ed[v][i].st);
            }
        }
    }
}

void BFSA(int n)
{
    int v, j = 0;
    for(int i = 1; i <= n; ++i)
    {
        vis[i] = 0; dis[i] = min(dis[i], II);
        que[i] = pair{dis[i], i};
    }
    sort(que + 1, que + 1 + n);
    while(j < n || (int)(q[0].size() + q[1].size()) > 0)
    {
        if((int)(q[0].size() + q[1].size()) == 0)
        {
            ++j;
            q[0].push(que[j].nd);
        }
        v = Get();
        while(j < n && que[j + 1].st <= dis[v])
        {
            ++j;
            q[0].push(que[j].nd);
        }
        if(vis[v]) continue;
        vis[v] = 1;
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(dis[ed[v][i].st] > dis[v] + ed[v][i].nd)
            {
                dis[ed[v][i].st] = dis[v] + ed[v][i].nd;
                q[ed[v][i].nd].push(ed[v][i].st);
            }
        }
    }
}

void Add(int a, int b, int v)
{
    a += N - 1; b += N + 1;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) ed[a + 1].pb(make_pair(v, 1));
        if(b % 2 == 1) ed[b - 1].pb(make_pair(v, 1));
        a /= 2; b /= 2;
    }
}

int Mi(int a, int b)
{
    a += N - 1; b += N + 1;
    int m1 = II, m2 = II;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0)
        {m1 = min(m1, dis[a + 1]); m2 = min(m2, d2[a + 1]);}
        if(b % 2 == 1)
        {m1 = min(m1, dis[b - 1]); m2 = min(m2, d2[b - 1]);}
        a /= 2; b /= 2;
    }
    return min(II, m1 + m2);
}

void Solve()
{
    int n, m, q, a, b;
    cin >> n;
    m = 2 * N - 1;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a >> b;
        ran[i] = pair{a, b};
        Add(a, b, i + N);
    }
    BFS(N + 1, m);
    for(int i = 1; i <= m; ++i) 
        d2[i] = dis[i];
    BFS(N + n, m);
    for(int i = 1; i <= m; ++i) 
        answer[i] = d2[i] + dis[i];
    for(int i = 1; i <= n; ++i)
        answer[i + N] = min(answer[i + N], Mi(ran[i].st, ran[i].nd) + 1);
    for(int i = 1; i <= m; ++i)
        dis[i] = answer[i];
    BFSA(m);
    for(int i = 1; i <= n; ++i)
    {
        answer[i] = dis[i + N];
        if(answer[i] >= II) answer[i] = -1;
    }
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        cin >> a;
        cout << answer[a] << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
    for(int i = 2; i < 2 * N; ++i)
        ed[i].pb(pair{i / 2, 0});
    Solve();

    return 0;
}