Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))

C = [0 for i in range(n)]   #Count
P = [-1 for i in range(n)]  #Patern
cp = 1  #current point
t = 0   #周期
while 1:
    #print('C = ', C)
    C[cp - 1] += 1
    if C[cp - 1] < 2:
        P[cp - 1] = t
    else:
        break
    cp = A[cp - 1]
    t += 1

pret = P[cp - 1]    #周期に入るまでの時間
t = t - pret
#print('pret = ', pret)
#print('t = ', t)
#print('P = ', P)

if k <= pret:
    l = k 
else:
    k = k - pret
    l = k % t
    P = list(map(lambda x: x - pret, P))
#print('P = ', P)

ans = 0
for i in range(n):
    if P[i] == l:
        ans = i + 1
        break
    else:
        pass
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
import math
from collections import defaultdict

N , K = map(int,input().split())
A = list(map(int,input().split()))

ha = defaultdict(int)
ans = defaultdict(int)
s = set()
s.add(1)
ss = set()
mod = 0
mod2 = 0
next = 0
ind = 0
flag = 0
while  True:
    if A[next] in s and flag == 0:
        flag = 1
        ha[0] = A[next]
        ans[0] = A[next]
        ss.add(A[next])
        ind = 0
        mod += 1
        continue
        # next = A[next] - 1 
    elif flag == 1:
        next = A[next] - 1
        ans[ind+1] = A[next]
        mod2 += 1
        if A[next] in ss :
            break
        ss.add(A[next])
        ind += 1
        continue

    ha[ind+1] = A[next]
    s.add(A[next])
    next = A[next] - 1
    mod += 1
    ind += 1

if mod >= K :
    print(ha[K % mod])
else:
    print(ans[(K-mod)%mod2])

#print(ha)
#print(ans)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N, K = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]

    bit_k = bin(K)[2:]

    telepo_list = [A_list]

    for _ in range(len(bit_k)-1):
        temp_list = telepo_list[-1]
        new_telep = [temp_list[i-1] for i in temp_list]
        telepo_list.append(new_telep)

    # print(telepo_list)

    goto = 1
    for i in range(len(bit_k)):
        temp_list = telepo_list[i]
        if ((K >> i) & 1):
            goto = temp_list[goto - 1]
            # print(i, goto)

    print(goto)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, K = map(int, input().split())
A = list(map(int, input().split()))

A = [a-1 for a in A]

b = bin(K)
D = {0:list(range(N))} # ダブリングマトリクス
D[1] = [A[D[0][i]] for i in range(N)]

for i in range(1, len(b)-2):
    D[2**i] = [D[2**(i-1)][D[2**(i-1)][j]] for j in range(N)]


n = 2**(len(b[2:])-1)
S = D[n][0] # 初期状態
keta = len(b[2:]) - 2
for j in range(len(b[3:])):
    k = 2**keta
    if b[j+3] == '1':
        S = D[k][S]
    keta -= 1

print(S+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))

T=[10**9]*(N+1)
label=[-1]*(N+1)
T[0]=1
label[1]=0
for i in range(1,N+1):
    T[i]=A[T[i-1]-1]
    if label[T[i]]>=0:
        poss=label[T[i]]
        pose=i
        break
    else:
        label[T[i]]=i

pos=K-poss-1
if pos>=0:
    pos=pos%(pose-poss)
    print(T[poss+pos+1])
else:
    print(T[K])

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x) - 1 for x in input().split()]

i = 0
T = []
S = set()
st = 0
while True:
    T.append(i)
    S.add(i)
    i = A[i]
    if i in S:
        st = T.index(i)
        break

# print(T)


idx = (K - st) % (len(T) - st)

if K > st:
    print(T[st + idx] + 1)
else:
    print(T[K] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

passed = [-1] * (n+1)
route = []
v = 1
while passed[v] == -1:
    passed[v] = len(route)
    route.append(v)
    v = a[v-1]

c = len(route) - passed[v]
l = passed[v]

if k < l:
    print(route[k])
else:
    k -= l
    k %= c
    print(route[l+k])

Submission status: Accepted

Solution code:
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    loop = [1]
    arrived = [0] * N
    now = 1
    arrived[now - 1] = 1

    for i in range(K):
        now = A[now - 1]
        if arrived[now - 1] == 0:
            arrived[now - 1] = 1
            loop.append(now)
        else:
            loop = loop[loop.index(now):]
            arrive = loop[(K - (i + 1)) % len(loop)]
            print(arrive)
            return

    print(now)

resolve()

Submission status: Accepted

Solution code:
'''
・基本的には素直なシミュレーションを行う
・ループ分のシミュレーションを省略することでTLEを回避
・Kは「残りのワープ数」と考える

K回のワープ中にループが含まれる場合、
1. 素直なシミュレーションを行う。このとき、Kを減算していく。
2. ループを検出したら、Kからループ長をできるだけ多く引くことで、計算を省略する。
3. 残りのステップ数、再度シミュレーションを行う
という手順で答えを求められる。
なお、ループが含まれない場合も1のみで答えを求められる。
'''

def main():
    N, K = map(int, input().split())
    A = [a-1 for a in map(int, input().split())]    # 0-indexed に変換
    B = [None]*N    # 何ステップ目に到達したかを記録。Noneなら未到達を表す
    now = 0         # 現在地
    step = 0        # ステップ数
    B[now] = 0      # 開始地点は、0ステップ目に到達済みとする
    while K:
        now = A[now]    # 現在地を更新 
        step += 1
        K -= 1
        if B[now] is not None:  # ループを検出したら...
            K %= (step - B[now])      # Kからループ長さを引けるだけ引く
        else:
            B[now] = step  # 到達したステップ数を記録
    print(now+1)    # 1-indexed に再変換

main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
sub = [0]*n
city = 0
all = []
roop = []
while sub[city] != 2:
  if sub[city] == 0:
    all.append(city+1)
  else:
    roop.append(city+1)
  sub[city] += 1
  city = A[city] -1
if len(all) > k:
  print(all[k])
else:
  print(roop[(k-(len(all)-len(roop)))%len(roop)])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ord_ = [-1] * (n + 1) # 何回目に訪れたか
homon = [] # 訪問した順番のリスト
current = 0
while ord_[current] == -1:
    ord_[current] = len(homon)
    homon.append(current)
    current = a[current] - 1

freq = len(homon) - ord_[current] # ループする都市数
n_before_loop = ord_[current] # ループするまでの都市数

if k < n_before_loop:
    print(homon[k] + 1)
else:
    k -= n_before_loop
    k %= freq
    print(homon[n_before_loop+k] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
log = []
visited = [False for i in range(n)]
now = a[0]-1
loop = False
for i in range(k-1):
    if visited[now] == True:
        loop = True
        break
    log.append(now)
    visited[now] = True
    now = a[now]-1
else:
    print(now+1)
if loop:
    for i in range(len(log)):
        if log[i] == now:
            first = len(log[:i])
            log_list = log[i:]
            loop_num = len(log_list)
            break
    k -= first
    k %= loop_num
    print(log_list[k-1]+1)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))

now = 1
town_list = [0]*n
town_list[0] = 1
tn_list = [1]

while(1):
    next = a[now-1]
    now = next
    if town_list[now-1] == 0:
        town_list[now-1] = 1
        tn_list.append(now)

    else:
        idx = tn_list.index(now)
        initial = tn_list[:idx]
        cycle = tn_list[idx:]
        break

if k >= len(initial):
    end_idx = (k-len(initial))%len(cycle)
    print(cycle[end_idx])
else:
    print(initial[k])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
li = [0]+list(map(int,input().split()))

memo = [-1]*(n+1)
start = 1
syuuki = 0
haji = 0

for i in range(k):
    if memo[start] != -1:
        syuuki = i - memo[start]
        haji = memo[start]
        break
    memo[start] = i
    start = li[start]
else:
    print(start)
    exit()

#print(syuuki,haji)
k-=haji
k%=syuuki
k+=haji

start = 1
for kk in range(k):
    start = li[start]
print(start)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ord_ = [-1] * (n + 1) # 何回目に訪れたか
s = []
current = 0
while ord_[current] == -1:
    ord_[current] = len(s)
    s.append(current)
    current = a[current] - 1
c = len(s) - ord_[current]
l = ord_[current]

if k < l:
    print(s[k] + 1)
else:
    k -= l
    k %= c
    print(s[l+k] + 1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
L = 60
dp = [[-1]*N for _ in range(L+1)]
for i,a in enumerate(A):
    dp[0][i] = a-1
for i in range(L):
    for j in range(N):
        dp[i+1][j] = dp[i][dp[i][j]]
ans = 0
for i in range(L):
    if K&(1<<i):
        ans = dp[i][ans]
print(ans+1)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    trans_list = [0] * n

    next_trans = num_list[0]
    for i in range(n):
        trans_list[i] = next_trans
        next_trans = num_list[next_trans-1]

    # print(trans_list)

    chcek_list = [INF] * n
    for i in range(n):
        if chcek_list[trans_list[i]-1] != INF:
            break
        chcek_list[trans_list[i]-1] = 1

    first_town = trans_list.index(trans_list[i])

    period = i - first_town

    if k <= n:
        print(trans_list[k-1])
    else:
        trans_list = trans_list[first_town:]
        trans_list = trans_list[:period]
        print(trans_list[(k-first_town)%period-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# input
N, K = map(int, input().split())
A = [0]
A.extend(list(map(int, input().split())))

# process
l = [0]*(N+1)
now = 1
i = 1
while l[now] == 0:
    l[now] = i
    now = A[now]
    i += 1

ans = 0
if K < l[now]:
    ans = l.index(K+1)
else:
    k = (K-l[now]+1)%(len([x for x in l if x!=0])-l[now]+1)
    ans = l.index(l[now]+k)

# output
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    # k<=10**18 < 2**60
    r = 60
    import math
    r = math.ceil(math.log2(k))
    idx = 0
    a = [a[i]-1 for i in range(n)]
    for i in range(r):
        if (k>>i)&1 == 1:
            idx = a[idx]
        a = [a[a[j]] for j in range(n)]
    print(idx+1)    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

pos = 0
visit = [0] * N
move = []
roop = []

while visit[pos] != 2:
    if visit[pos] == 0:
        move.append(pos)
    else:
        roop.append(pos)

    visit[pos] += 1
    pos = A[pos] - 1

if len(move) > K:
    print(move[K] + 1)
else:
    print(roop[(K- (len(move) - len(roop))) % len(roop)] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(lambda s: int(s) - 1, input().split()))

cur = 0
while k > 0:
    if k % 2 == 1:
        cur = a[cur]
    next = [a[a[i]] for i in range(n)]
    a = next
    k //= 2
print(cur + 1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N,K = map(int,readline().split())
A = [0] + list(map(int,readline().split()))
c = 1
while K:
  if K & 1:
    c = A[c]
  A = [A[A[i]] for i in range(len(A))]
  K >>= 1
print(c)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))

visit = [-1]*(N+1)
history = []
v, cnt = 1, 0
while visit[v] == -1:
  visit[v] = cnt
  history.append(v)
  v = A[v-1]
  cnt += 1
period = cnt - visit[v]
l = visit[v]

if K < l:
  print(history[K])
else:
  K -= l
  K %= period
  print(history[l+K])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
#  = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

ord_ = [-1] * (n + 1)
s = []
v = 1
while ord_[v] == -1:
    ord_[v] = len(s)
    s.append(v)
    v = a[v-1]
c = len(s) - ord_[v]
l = ord_[v]

if k < l:
    print(s[k])
else:
    k -= l
    k %= c
    print(s[l+k])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a = list(map(int,input().split()))
visit = []
visit = [0]*n
pos=0
move=[]
roop=[]
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos]+=1
    pos = a[pos]-1
if len(move)>k:
    print(move[k]+1)
else:
    mod = (k-(len(move)-len(roop)))%len(roop)
    print(roop[mod]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    start = 0
    visited = {start}
    visited_list = [start]
    while True:
        start = a[start] - 1
        if start in visited:
            loop_start = start
            break
        visited_list.append(start)
        visited.add(start)
    p = visited_list.index(loop_start)
    loop = visited_list[p:]
    if k < p:
        print(visited_list[k] + 1)
    else:
        print(loop[(k - p) % len(loop)] + 1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
n, k = map(int, input().split())
a = list(map(int, input().split())) 

visited = [None]*n
cur = 0
for i in range(k):
    if visited[cur] is None:
        visited[cur] = i
        cur = a[cur]-1
    else:
        break
else:
    print(cur+1)
    sys.exit()

k -= i
k %= i-visited[cur]

for i in range(k):
    cur = a[cur]-1

print(cur+1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools

def main():
  n,k = map(int, input().split())
  a = list(map(int,sys.stdin.readline().split()))

  now = 0
  times = 0
  visit =[[0],[-1 for _ in range(n)]]
  visit[1][0] = 0
  roop = 0
  roop_start = 0

  for _ in range(k):
    times += 1
    now = a[now] - 1

    if visit[1][now] != -1:
      roop_start = visit[1][now] #ループが始めった待ちの最初に訪れた時に何回ループしていたかをroop_startに代入
      roop = times - roop_start #何個の町でループしてるかをroopに代入
      break
    else:
      visit[0].append(now)
      visit[1][now] = len(visit[0]) - 1

  if roop > 0:
    k = (k - roop_start) % roop

  # print(roop_start)
  # print(roop)
  # print(k)
  # print(visit[0])
  print(visit[0][roop_start + k] + 1)

  # now = 0
  # for _ in range(roop_start):
  #   now = a[now] - 1

  # for _ in range(k):
  #   now = a[now] -1

  # print(now+1)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# 初期入力
from collections import Counter
from copy import deepcopy
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
connection ={}
for i,v in enumerate(A):
    connection[i+1] =v 

#巡回してるか
passed=[1]
nex =connection[1]
lap =[]
lap_num =0
pass_set =set(passed)
for i in range(1,N+1):
    passed.append(nex)
    if nex not in pass_set:
        pass_set.add(nex)
        nex =connection[nex]
    else:
        #lap =deepcopy(passed)
        break
#巡回している部分の町の数    
indx_s =passed.index(nex) +1
indx_f =len(passed)
lap_num =indx_f -indx_s

if indx_f < K:
    mod =(K -indx_s) % lap_num
    ans =passed[indx_s +mod]
else:
    ans =passed[K]
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int,input().split()))
pos = 0
visit = [0] * n
move = []
roop = []
while visit[pos] !=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = a[pos] - 1

if len(move)>k:
    print(move[k]+1)
else:
    print(roop[(k-(len(move)-len(roop)))%len(roop)]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))

Town = []
#まだ訪れていない町は-1
rec = [-1] * (n+1)
idx = 1
#周期までループをまわす
while (rec[idx] == -1):
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

#周期前
Exce = rec[idx]
#周期内
Cycl = len(Town) - Exce

if Exce > k:
    print(Town[k])
else:
    Warp = (k - Exce) % Cycl
    print(Town[Exce+Warp])

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI_()

    ord = [-1]*N

    city = 0
    cnt = 0
    teleport_path = []
    while ord[city]==-1:
        ord[city] = cnt
        teleport_path.append(city)
        city = A[city]
        cnt += 1
    loop_head = ord[city]
    loop_length = len(teleport_path) - loop_head
    # print(teleport_path, loop_head, loop_length)

    if K-1<loop_head:
        print(teleport_path[K]+1)
    else:
        K = loop_head + (K-loop_head)%loop_length
        print(teleport_path[K]+1)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Alist = list(map(int, input().split()))

# ループする数を求める
loop_num = 2 * 10 ** 5
loop_start_point = -1
point = 1
count_list = [-1] * N

for i in range(K):
    #print("point:", point)
    count_list[point - 1] = i
    nextPoint = Alist[point - 1]

    if count_list[nextPoint - 1] != -1:
        loop_start_point = nextPoint
        loop_num = i - count_list[loop_start_point - 1] + 1
        break
    
    point = nextPoint

if loop_start_point == -1:
    print(point)
else:
    point = loop_start_point
    progress_num = (K - count_list[loop_start_point-1]) % loop_num
    for i in range(progress_num):
        point = Alist[point - 1]
    #print("pro:", progress_num)
    #print("ls:", loop_start_point)
    #print("ln:", loop_num)
    print(point)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    nw = 1
    lp0 = [1]
    lpl = {1}
    for i in range(N):
        nw = A[nw-1]
        if nw in lpl:
            break
        else:
            lp0.append(nw)
            lpl.add(nw)
    lpc = i+1 - lp0.index(nw)
    lp = lp0[-lpc:]

    if K<=len(lp0)-1:
        print(lp0[K])
    else:
        K-= len(lp0)-1
        K=K%lpc - 1
        print(lp[K])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[~-int(x) for x in input().split()]

p,c=[-1]*N,0
for i in range(N+1):
  if p[c]==-1:
    p[c]=i
    c=A[c]
  else:
    break

print(1+p.index(p[c]+(K-p[c])%(i-p[c]) if K>=p[c] else K))

Submission status: Accepted

Solution code:
def main():
    
    IN = [int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    N = IN[0]
    K = IN[1]

    #移動経路を記録する配列
    l = []
    l.append(1)
    #次のポータルのindexを指す変数
    nextInd = 1
    #1回遷移したかどうかを記録する配列
    mark = [False] * N
    mark[0] = True
    #ループ直前までに何回移動したかを記録する変数
    startLoopCount = 0
    #移動経路の記録、次のindexが1回行ったことがある場合に終了
    while True:
        nextInd = A[nextInd-1]
        if mark[nextInd-1]:
            startLoopCount = l.index(nextInd)
            break
        l.append(nextInd)
        mark[nextInd-1] = True
    #遷移部分とLoop部分と分ける
    move = l[0:startLoopCount]
    loop = l[startLoopCount:len(l)]

    # print(startLoopCount)
    # print(move)
    # print(loop)
    
    if K < startLoopCount:
        print(move[K])
        return
    index = (K - startLoopCount) % len(loop)
    print(loop[index])
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    As = list(map(int, input().split()))
    i = 0
    visit = [0]*n
    move = []
    roop = []
    while visit[i] != 2:
        if visit[i] == 0:
            move.append(i)
        else:
            roop.append(i)
        visit[i] += 1
        i = As[i] - 1

    if len(move) > k:
        ans = move[k] + 1
    else:
        ans = roop[(k-(len(move)-len(roop))) % len(roop)]+1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))
C=[1]
s=set([1])
for i in range(N):
  if A[C[i]-1] in s:
    l=C.index(A[C[i]-1])+1
    break
  else:
    C.append(A[C[i]-1])
    s.add(A[C[i]-1])
if K+1<=l:
  print(C[K])
else:
  print(C[l-1+(K+1-l)%(len(C)-l+1)])

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, K = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]
    order_dict = dict(zip(range(1,N+1),A_list))

    foot_print = [-1 for _ in range(N+1)]
    loop_que = collections.deque([1])

    goto = 1

    while foot_print[goto] == -1:
        foot_print[goto] = 1
        goto = order_dict[goto]
        loop_que.append(goto) 

    loop_start = loop_que.index(goto) + 1
    loop_len = len(loop_que) - loop_start

    # print(loop_que)
    # print(loop_start, loop_len)


    data_list = list(loop_que)
    if K >= len(loop_que):
        temp_K = K - loop_start + 1
        temp_K %= loop_len
        temp_loop = data_list[loop_start-1:-1]
        print(temp_loop[temp_K])
    else:

        print(data_list[K])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = [i - 1 for i in map(int, readline().split())]

m = 60
d = [A]
pre = A
for i in range(m):
    current = [pre[pre[j]] for j in range(n)]
    d.append(current)
    pre = current

route = 0
for i in range(m-1, -1, -1):
    if k >= (x := 1 << i):
        route = d[i][route]
        k -= x
print(route+1)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K=map(int,input().strip().split())
A=[0]+list(map(int,input().strip().split()))

G=defaultdict(list)
prev=1

visited=set()
visited.add(1)

next=A[1]
while(not next in visited):
    G[prev].append(next)
    prev=next
    visited.add(next)
    next=A[next]
G[prev].append(next)
#loop starts from next
#calculate length = number of nodes in loop from next to prev

origin=next
next=G[origin][0]
cnt=0 ##length of loop
while(next!=origin):
    cnt+=1
    next=G[next][0]
##get Distance require to travel from town 1 to origin.
cnt+=1
origin1=1
next=G[1][0]
dist=0
while(next!=origin):
    dist+=1
    next=G[next][0]
dist+=1
if K<dist:
    cnt =0
    origin=1
    next=origin
    while(cnt!=K):
        cnt+=1
        next=G[next][0]
    print(next)
else:
    K=K-dist
    N=K%cnt
#travel N nodes from origin i.e start of the loop
    cnt=0
    next=origin
    while(cnt!=N):
        cnt+=1
        next=G[next][0]
    print(next)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# A[i]: iの次の要素
# M: 何個先まで調べたいか
class Doubling(object):
    def __init__(self,A,M):
        self.N = len(A)
        self.kmax = M.bit_length()
        # nex[i][k]: i番目の2^k先
        self.nex = [[-1]*self.kmax for _ in range(N)]
        for i in range(N):
            self.nex[i][0] = A[i]
        
        for k in range(1,self.kmax):
            for i in range(N):
                if self.nex[i][k-1] == -1:
                    self.nex[i][k] = -1
                else:
                    self.nex[i][k] = self.nex[self.nex[i][k-1]][k-1]
    
    # i番目の要素のx個先
    def query(self,i,x):
        L = x.bit_length()
        for k in range(L)[::-1]:
            if i == -1:
                break
            if (x >> k) & 1:
                i = self.nex[i][k]
        return i

N,K = LI()
A = LI()
A = list(map(lambda x: x-1, A))

d = Doubling(A,K)
print(d.query(0,K)+1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# A[i]: iの次の要素
# M: 何個先まで調べたいか
class Doubling(object):
    def __init__(self,A,M):
        self.N = len(A)
        self.kmax = M.bit_length()
        # nex[i][k]: i番目の2^k先
        self.nex = [[-1]*self.kmax for _ in range(N)]
        for i in range(N):
            self.nex[i][0] = A[i]
        
        for k in range(1,self.kmax):
            for i in range(N):
                if self.nex[i][k-1] == -1:
                    self.nex[i][k] = -1
                else:
                    self.nex[i][k] = self.nex[self.nex[i][k-1]][k-1]
    
    # i番目の要素のx個先
    def query(self,i,x):
        for k in range(self.kmax)[::-1]:
            if i == -1:
                break
            if (x >> k) & 1:
                i = self.nex[i][k]
        return i

N,K = LI()
A = LI()
A = list(map(lambda x: x-1, A))

d = Doubling(A,K)
print(d.query(0,K)+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
t=[[0 for i in range(n)] for j in range(64)]
for i in range(64):
    for j in range(n):
        if i == 0:
            t[i][j]=a[j]
        else:
            t[i][j]=t[i-1][t[i-1][j]-1]
ans=1
for i in range(64):
    r = k%2
    k = k//2
    if r == 1:
        ans = t[i][ans-1]
    if k == 0:
        print(ans)
        exit()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
check=[[] for i in range(n)]
c=0
g=1
tmp=[]
cy=[]
non=[]

while c<n:
    if check[g-1]==[]:
        c+=1
        tmp.append(g)
        check[g - 1].append(c)
        g=a[g-1]
    else:
        cy=tmp[(check[g-1][0]-1):]
        non=tmp[:(check[g-1][0]-1)]
        break
if k<len(non):
    print(non[k])
    exit()
k-=len(non)
k%=len(cy)


print(cy[k])

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
 
def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    A = [int(x) for x in stdin.readline().rstrip().split()]
    X = 1
    L = [1]
    if A[0] == 1:
        print(1)
        exit()
    if N >= K :
        for i in range(K):
            X = A[X-1]
        print(X)
        exit()
    else:
        for i in range(N):
            X = A[X-1]
            L += [X]
        #print('L',L)#OK
        C = np.zeros(N)
        for i in range(N):
            if C[L[i]-1] == 0:
                C[L[i]-1] += 1
                #print('C,i',C,i)
            else:
                break
        #print('C',C)
        #print('i+1',i+1)#Roop 回数　When Roop Goal
        #print('L[i+1]',L[i+1])#Roop initial Number
        S = L.index(L[i+1])
        #print('S',S)#When Roop Start ,Roop times
        #print(K - i-1)#Remain K
        #print('i + 1 -S',i + 1 - S)#Roop Cycle
        K = (K - i-1)%(i+1 - S)
        #print(K)
        print(L[S+K])
        
main()

Submission status: Accepted

Solution code:
def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    isVisited = [False for i in range(N)]
    i = 0
    while i<K:
        # まず進む
        now = A[now]-1
        # 道順登録
        #if now not in history:
        if isVisited[now] == False:
            history.append(now)
            isVisited[now] = True
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()

Submission status: Accepted

Solution code:
import collections

def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]

[n,k] = getlsi()
a = getlsi()

dic = collections.defaultdict(int)

now = 1

cnt = 1
while dic[now] == 0:
    dic[now] = cnt
    now = a[now-1]
    cnt += 1
lp = cnt - dic[now]
if k <= dic[now]:
    next = 1
    for i in range(k):
        next = a[next-1]
    print(next)
else:
    next = 1
    tmp = (k+1 - dic[now]) % lp
    #print(tmp)
    for i in range(dic[now]+ tmp-1):
        #print(next)
        next = a[next-1]
    print(next)
#else: