TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Teleporter

問題

D – Teleporter
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

// dp[p][i] :=

int main() {
  ll N, K;
  cin >> N >> K;

  vector<ll> A(N);
  rep(i, N) {
    cin >> A[i];
    A[i]--;
  }

  // K が 2 の何乗かを計算する。
  int P = 1;
  while((1LL << P) <= K) {
    P++;
  }

  // dp[p][i] := i番目のから2^p回移動した先の町
  vector<vector<int>> dp(P, vector<int>(N));

  // 初期値を入れる
  rep(i, N) { dp[0][i] = A[i]; }

  // dpを回す
  rep(p, P - 1) {
    rep(i, N) { dp[p + 1][i] = dp[p][dp[p][i]]; }
  }

  // K回、回す
  int ans = 0;
  rep(i, P) {
    if(K & (1LL << i)) {
      ans = dp[i][ans];
    }
  }

  cout << ans + 1 << endl;
  return 0;
}