제출 #1217822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217822		escobrand	Passport (JOI23_passport)	C++20	0 / 100	338 ms	85140 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];
int d[maxn][3],w;
int c[maxn];
int 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[1][0] = d[n][1] = 0;

    deque<pii>q;
    q.push_front({0,1});
    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)
        {
            if(k.se)e[k.fi] = i;
            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,n});
    while(q.size())
    {
      i = q.front().se;
      w = q.front().fi;
      q.pop_front();
      if(c[i] == 2)continue;
      c[i] = 2;
      for(auto k : adj[i])
      {
        if(d[k.fi][1] > w + k.se)
        {
            d[k.fi][1] = w + k.se;
            d[k.fi][2] = d[i][2] + (e[k.fi] == i);
//            cout<<i<<' '<<k.fi<<' '<<d[k.fi][2]<<'\n';
            if(k.se)q.eb({d[k.fi][1],k.fi});
            else q.push_front({d[k.fi][1],k.fi});
        }
      }
    }

//    for(i = 1;i<=n;i++)
//    {
//        cout<<d[i][0]<<' '<<d[i][1]<<' '<<d[i][2]<<' '<<min({d[i][0] + d[i][1] - d[i][2], d[i][0] + d[1][1], d[i][1] + d[n][0]})<<'\n';
//    }


    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][2], d[i][0] + d[1][1], d[i][1] + d[n][0]})<<'\n';
    }

    return 0;
}

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