Submission #959516

#	Time	Username	Problem	Language	Result	Execution time	Memory
959516		edogawa_something	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2064 ms	30424 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
const ll M=2e5+10;
const ll inf=2e18;
ll n,k,q,l[M],dis[M];
vii lev[M],v[M];
set<ll>s;
void bfs(ll x){
  for(int i=1;i<=n;i++)
  dis[i]=inf;
  dis[x]=0;
  queue<ll>q;
  q.push(x);
  while(!q.empty()){
    ll p=q.front();
    q.pop();
    for(auto it:v[p]){
      if(dis[it]==inf)
      dis[it]=dis[p]+1,q.push(it);
    }
  }
}
void add(ll x,ll y,ll z){
  auto it=s.upper_bound(-x);
  auto itt=s.upper_bound(x);
  ll nxt,prev;
  nxt=prev=inf;
  if(itt!=s.end()){
    nxt=*itt;
  }
  if(it!=s.end()&&*it<0){
    prev=-*it;
  }
  if(nxt!=inf){
    if(y<nxt)
    v[x].pb(y),v[y].pb(x);
    else
    v[x].pb(nxt),v[nxt].pb(x);
  }
  else if(y!=inf)
  v[x].pb(y),v[y].pb(x);
  if(prev!=inf){
    if(z<prev)
    v[x].pb(prev),v[prev].pb(x);
  }
  s.insert(x),s.insert(-x);
}
int main(){
  ios_base::sync_with_stdio(0),cin.tie(0);
  cin>>n>>k>>q;
  for(int i=0;i<n;i++)
  cin>>l[i+1],lev[l[i+1]].pb(i+1);
  for(int i=k;i>=1;i--){
    for(int j=0;j<lev[i].size();j++){
      ll y,z;
      y=inf,z=-inf;
      if(j>0)
      z=lev[i][j-1];
      if(j<lev[i].size()-1)
      y=lev[i][j+1];
      add(lev[i][j],y,z);
    }
  }
  while(q--){
    ll a,b;
    cin>>a>>b;
    bfs(a);
    cout<<dis[b]-1<<'\n';
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55