Submission #1217820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217820		escobrand	Passport (JOI23_passport)	C++20	6 / 100	197 ms	77328 KiB

passport

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long
#define fi first
#define se second
int t,n,i,m,u,v,tt;
const int maxn = 1e6 + 10;
typedef pair<int,int> pii;
vector<pii> adj[maxn];
int id1[maxn];
int d[maxn],w;
int c[maxn];
bool e[maxn];

void build1(int i,int l,int r)
{
  if(id1[i] == 0)id1[i] = ++t;
  if(l == r)
  {
    adj[id1[i]].eb({l,0});
  }
  else
  {
    int mid =(l + r)/2,ii = i + i;
    build1(ii,l,mid);
    build1(ii+1,mid+1,r);
    adj[id1[i]].eb({id1[ii],0});
    adj[id1[i]].eb({id1[ii+1],0});
  }
}

void add1(int i,int l,int r,int tl,int tr,int from)
{
  if(tl > tr || tl > r || tr < l)return;
  if(tl >= l && tr <= r)
  {
    adj[from].eb({id1[i],1});
    return;
  }
  int mid =(tl + tr)/2,ii = i + i;
  add1(ii,l,r,tl,mid,from);
  add1(ii+1,l,r,mid+1,tr,from);
}

deque<pii>q;
int bfs(int id)
{
    for(i = 1;i<=t;i++)d[i] = 1e9;
    d[id] = 0;
    q.push_front({0,id});
    ++tt;
    while(q.size())
    {
      i = q.front().se;
      w = q.front().fi;
      q.pop_front();
      if(c[i] == tt)continue;
      c[i] = tt;
      for(auto k : adj[i])
      {
        if(d[k.fi] > w + k.se)
        {
            d[k.fi] = w + k.se;
            if(k.se)q.eb({d[k.fi],k.fi});
            else q.push_front({d[k.fi],k.fi});
        }
      }
    }
    if(max(d[1],d[n]) == 1e9)return -1;
    return max(d[1],d[n]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    t = n;
    build1(1,1,n);
    for(i = 1;i<=n;i++)
    {
      cin>>u>>v;
      add1(1,u,v,1,n,i);
    }

    cin>>m;
    while(m--)
    {
        cin>>i;
        cout<<bfs(i)<<'\n';
    }

    return 0;
}

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