Submission #1308141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308141		thnhann	Passport (JOI23_passport)	C++20	0 / 100	1670 ms	1114112 KiB

passport

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=2e5;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

int L[nmax + 5];
int R[nmax + 5];
int ans[nmax + 5];

vector<int>adj[nmax + 5];
vector<int>rev_adj[nmax + 5];

int n,q;

ii range[nmax + 5];

signed main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin >> n;
   for(int i=1;i<=n;i++)
   {
       cin >> range[i].fi >> range[i].se;
   }

   for(int i=1;i<=n;i++)
   {
       for(int point = range[i].fi; point <= range[i].se;point++)
        rev_adj[point].pb(i);
   }

   for(int i=1;i<=n;i++)
   {
       L[i] = R[i] = ans[i] = inf;
   }

   queue<int>q;

   for(int i=1;i<=n;i++)
   {
       if(range[i].fi == 1)
       {
           L[i] = 1;
           q.push(i);
       }
   }

   while(!q.empty())
   {
       int u = q.front();
       q.pop();
       for(auto v:rev_adj[u])
       {
           if(L[v] > L[u] + 1)
           {
               L[v] = L[u] + 1;
               q.push(v);
           }
       }
   }


   for(int i=1;i<=n;i++)
   {
       if(range[i].se == n)
       {
           R[i] = 1;
           q.push(i);
       }
   }

   while(!q.empty())
   {
       int u = q.front();
       q.pop();
       for(auto v:rev_adj[u])
       {
           if(R[v] > R[u] + 1)
           {
               R[v] = R[u] + 1;
               q.push(v);
           }
       }
   }



   for(int i=1;i<=n;i++)
   {
       if(L[i] != inf && R[i] != inf)
       {
           ans[i] = L[i] + R[i] - 1;
           q.push(i);
       }
       else
        ans[i] = inf;
   }

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto v:rev_adj[u])
        {
            if(ans[v] > ans[u] + 1)
            {
                ans[v] = ans[u] + 1;
                q.push(v);
            }
        }
    }

    int query;
    cin >> query;
    while(query--)
    {
        int x;
        cin >> x;
        if(ans[x] == inf) cout << -1;
        else cout << ans[x];
        el;
    }

}
//  "Can i get a kiss? And can u make it last forever?"

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