Submission #1219177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219177		escobrand	Passport (JOI23_passport)	C++20	0 / 100	24 ms	47172 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],adj2[maxn];
int id2[maxn],d[maxn][3],w;

void build2(int i,int l,int r)
{
  if(id2[i] == 0)id2[i] = ++t;
  if(l == r)
  {
    adj[l].eb({id2[i],0});
    adj2[id2[i]].eb({l,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});
    adj2[id2[i]].eb({id2[ii],0});
    adj2[id2[i]].eb({id2[ii+1],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});
    adj2[from].eb({id2[i],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] = d[i][2] = 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(w > d[i][0])continue;
      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();
      if(w > d[i][1])continue;
      for(auto k : adj[i])
      {
        if(d[k.fi][1] > w + k.se)
        {
            d[k.fi][1] = w + k.se;
            if(k.se)q.eb({d[k.fi][1],k.fi});
            else q.push_front({d[k.fi][1],k.fi});
        }
      }
    }
    priority_queue<pii,vector<pii>,greater<>>p;
    for(i = 1;i<=n;i++)
    {
      d[i][2] = max(d[i][0] + d[i][1]-1,1);
      p.push({d[i][2],i});
    }
    
    while(p.size())
    {
      i = p.top().se;
      w = p.top().fi;
      p.pop();
      if(w > d[i][2])continue;
      for(auto k : adj[i])
      {
        if(d[k.fi][2] > w + k.se)
        {
            d[k.fi][2] = w + k.se;
            p.push({d[k.fi][2],k.fi});
        }
      }
    }
    cin>>m;
    while(m--)
    {
      cin>>i;
      cout<<(d[i][2] > 9e8? -1 :d[i][2])<<'\n';
    }

    return 0;
}

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