Submission #1326930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326930		animal_migration	Passport (JOI23_passport)	C++17	100 / 100	832 ms	168016 KiB

passport

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define eb emplace_back
#define rep(x,y,z) for (int x=y;x<z;x++)
const int inf=1e9+7;
const int mn=2e5+7;
const int mm=2e6;
vector<pii> G[mm];
int seg[mn*4];
int id=0;

#define lc (i*2+1)
#define rc (i*2+2)
#define m ((l+r)/2)

void bld(int i, int l, int r){
  seg[i]=id++;
  if (l==r){
    G[seg[i]].eb(l,0);
    return;
  }
  bld(lc,l,m);
  bld(rc,m+1,r);
  G[seg[i]].eb(seg[lc],0);
  G[seg[i]].eb(seg[rc],0);
  // cout<<seg[i]<<" -> "<<seg[lc]<<' '<<seg[rc]<<'\n';
}

void add(int i, int l, int r, int ql, int qr, int x, int v){
  if (l>qr||r<ql) return;
  if (ql<=l&&r<=qr){
    G[x].eb(seg[i],v);
    return;
  }
  add(lc,l,m,ql,qr,x,v);
  add(rc,m+1,r,ql,qr,x,v);
}

#undef lc
#undef rc
#undef m

void rrr(){
  vector<vector<pii>> adj(id);
  rep(i,0,id){
    for (auto [j,w]:G[i]){
      adj[j].eb(i,w);
    }
  }
  rep(i,0,id){
    // cout<<i<<": ";
    adj[i].swap(G[i]);
    // for (auto [j,w]:G[i]) cout<<j<<','<<w<<" ";
    // cout<<'\n';
  }
}

void rmm(){
  rep(i,0,id) vector<pii>().swap(G[i]);
  id=0;
}

void dij(int x, vector<bool> &vis, vector<int> &dis){
  priority_queue<pii,vector<pii>,greater<pii>> que;
  que.push({0,x});
  dis[x]=0;
  while (!que.empty()){
    auto [d,u]=que.top();
    // cout<<d<<' '<<u<<"*\n";
    que.pop();
    if (vis[u]) continue;
    vis[u]=1;
    // cout<<u<<": "<<dis[u]<<'\n';
    for (auto [v,w]:G[u]){
      if (dis[v]>dis[u]+w){
        dis[v]=dis[u]+w;
        que.push({dis[v],v});
      }
    }
  }
}

signed main(){
  cin.tie(nullptr)->ios::sync_with_stdio(0);
  int n;
  cin>>n;
  vector<int> ll(n), rr(n);
  id=n;
  bld(0,0,n-1);
  rep(i,0,n){
    cin>>ll[i]>>rr[i];
    ll[i]--; rr[i]--;
    add(0,0,n-1,ll[i],rr[i],i,1);
  }
  rrr();
  vector<int> d1(id,inf), d2(id,inf);
  vector<bool> v1(id,0), v2(id,0);
  dij(0,v1,d1);
  dij(n-1,v2,d2);
  rep(i,0,n){
    if (ll[i]==0){
      d1[i]=1;
    }
    if (rr[i]==n-1){
      d2[i]=1;
    }
    // cout<<i<<": "<<d1[i]<<", "<<d2[i]<<'\n';
    G[id].eb(i,d1[i]+d2[i]-1);
  }
  id++;
  vector<int> dis(id,inf);
  vector<bool> vis(id,0);
  dij(id-1,vis,dis);
  int q;
  cin>>q;
  while (q--){
    int x;
    cin>>x;
    x--;
    cout<<(dis[x]>=inf-3?-1:dis[x])<<'\n';
  }
  return 0;
}

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