Submission #1218163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218163		escobrand	Passport (JOI23_passport)	C++20	6 / 100	360 ms	82280 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;
const int maxn = 1e6 + 10;
typedef pair<int,int> pii;
vector<pii> adj[maxn];
int id2[maxn],d[maxn][2],w,c[maxn],e[maxn];

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

void add2(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[id2[i]].eb({from,1});
    return;
  }
  int mid =(tl + tr)/2,ii = i + i;
  add2(ii,l,r,tl,mid,from);
  add2(ii+1,l,r,mid+1,tr,from);
}


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


    cin>>n;
    t = n;
    build2(1,1,n);
    for(i = 1;i<=n;i++)
    {
      cin>>u>>v;
      add2(1,u,v,1,n,i);
    }

    for(i = 1;i<=t;i++)
    {
      d[i][0] = d[i][1] = 1e9;
    }
    d[n][0] = d[1][1] = 0;

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

    cin>>m;
    while(m--)
    {
        cin>>i;
        if(d[i][0] + d[i][1] >= 1e9)
        {
            cout<<-1<<'\n';
            continue;
        }
        cout<<min({d[i][0] + d[i][1],d[i][0] + d[n][1], d[i][1] + d[1][0]})<<'\n';
    }

    return 0;
}

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