ABC030-D へんてこ辞書

using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
int n,a;
string k;
int b[100001];
int num[100001];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n>>a;a--;
  cin>>k;
  for(int i=0;i<n;i++){
    cin>>b[i];b[i]--;
  }
  if((int)k.size()<=7){
    ll h=stoi(k);
    int ans=a;
    for(int i=0;i<h;i++){
      ans=b[ans];
    }
    print(ans+1);
  }else{
    for(int i=0;i<n;i++){
      num[i]=-1;
    }
    int now=a;
    int t,circle;
    for(int i=0;;i++){
      if(num[now]!=-1){
        t=num[now];
        circle=i-t;
        break;
      }
      num[now]=i;
      now=b[now];
    }
    int h=0;
    for(int i=0;i<(int)k.size();i++){
      h=(h*10+(int)(k[i]-'0'))%circle;
    }
    h-=t;
    if(h<0){
      int temp=-h/circle;
      temp++;
      h+=circle*temp;
    }
    int ans=a;
    for(int i=0;i<t+h;i++){
      ans=b[ans];
    }
    print(ans+1);
  }
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

• 最初、ダブリングだーって思って提出したらWAで、なんでやって制約見たら卒倒した。
• 閉路に入る前と後に分けるのが重要で、modとった後に閉路に入る前の分だけ引く。
• これでマイナスだとダメなので正の数に直してあげましょう。