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 = [0] + list(map(int,input().split()))

now = 1
route = []
dic = {}
cnt = 0
entry = []
loop = []

while True:
  cnt += 1
  now = A[now]
  route.append(now)
  if now in dic:
    entry = route[:dic[now]]
    loop = route[dic[now]:]
    break
  dic[now] = cnt

if K <= len(entry):
  print(entry[K - 1])
else:
  K -= 1
  K -= len(entry)
  K %= len(loop)
  print(loop[K])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [-1] + list(map(int, input().split()))

visited = [0] * (1 + n)
curr = 1
while k:
    if visited[curr]:
        break
    else:
        visited[curr] = k
        curr = a[curr]
        k -= 1
        if k == 0:
            print(curr)
            exit()
repeat = visited[curr] - k
k = k % repeat
while k:
    curr = a[curr]
    k -= 1
print(curr)

Submission status: Accepted

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

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

ord = [-1 for _ in range(N)]
ord[0] = 0
v = A[0]-1
root = [0]

while ord[v] == -1:
    #ordに何回目のワープかが記録される
    ord[v] = len(root)
        #ワープの軌跡を記録
    root.append(v)

    #次の地点にワープ5
    v = A[v]-1

# print(ord)
# print(root)

#ord[v]:最終地点（ループ起点 or ループ前の道のり）
# ループ起点までの余分な手
l = ord[v]
#ループ距離
c = len(root) - l

if K < l:
    #ループ前にワープが終了した場合、最終地点を出力
    ans = root[K]
else:
    #ループする回数を計算
    # はじめにループ起点までの余分手をKから引く
    K -= l
    # ループのmodを計算
    K %= c
    # 余分手＋ループのmodの位置の国に止まる
    ans = root[l+K]
print(ans+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [1]
C = [1] + [0] * (N - 1)
i = 0

while C[A[i] - 1] == 0:
    B.append(A[i])
    C[A[i] - 1] = 1
    i = A[i] - 1

ans = 0
for j in range(len(B)):
    if B[j] == A[i]:
        ans += j

if (len(B) - ans != 0) and (K - ans > 0):
    ans += (K - ans) % (len(B) - ans)
elif K - ans <= 0:
    ans = K


print(B[ans])

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K = map(int,input().split())
N_List = list(map(int,input().split()))

N_Dict = defaultdict(int)
N_Dict[1] = 1
Pos = N_List[0]
for i in range(N):
    N_Dict[Pos] += 1
    if N_Dict[Pos] == 2:
        break
    else:
        Pos = N_List[Pos - 1]

##ループ始点がPosに入っている状態
##ループがどのくらいの長さか知りたい
CPos = Pos
flg = 0
Loop_List = [CPos]
while flg == 0:
    CPos = N_List[CPos-1]
    if CPos != Pos:
        Loop_List.append(CPos)
    else:
        flg = 1

##ループの始点に至るまでの長さを求める
FL = len(N_Dict) - len(Loop_List) 
if FL <= K:
    ans = Loop_List[(K - FL) % len(Loop_List)]
else:
    ans =list(N_Dict.keys())[K]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n, k = map(int, input().split(" "))
    a = list(map(int, input().split(" ")))
    s = []
    ord = [-1]*(n+1)
    u = 1
    while ord[u] == -1:
        ord[u] = len(s)
        s.append(u)
        u = a[u-1]
    l = len(s) - ord[u]
    if k < ord[u]:
        print(s[k])
    else:
        print(s[(k-ord[u])%l+ord[u]])

'''
def main():
    n, k = map(int, input().split(" "))
    a = list(map(lambda i: int(i)-1, input().split(" ")))
    s = [0]
    d = defaultdict(lambda:0)
    x = a[0]
    for i in range(n):
        s.append(x)
        x = a[x]

    bb=None
    for i in range(n):
        d[s[i]] += 1
        if d[s[i]] ==2:
            bb=s[i]
            break

    cc = s.index(bb)
    s[cc]=-1
    dd = s.index(bb)
    loop_len = dd-cc
    s[cc]=s[dd]
        
    if bb ==None or k < cc:
        print(s[k]+1)
    else:
        y = (k-cc) % loop_len
        print(s[y+cc]+1)
'''
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    n, k = map(int, input().split(" "))
    a = list(map(lambda i: int(i)-1, input().split(" ")))
    s = [0]
    d = defaultdict(lambda:0)
    x = a[0]
    for i in range(n):
        s.append(x)
        x = a[x]

    bb=None
    for i in range(n):
        d[s[i]] += 1
        if d[s[i]] ==2:
            bb=s[i]
            break

    cc = s.index(bb)
    s[cc]=-1
    dd = s.index(bb)
    loop_len = dd-cc
    s[cc]=s[dd]
        
    if bb ==None or k < cc:
        print(s[k]+1)
    else:
        y = (k-cc) % loop_len
        print(s[y+cc]+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A = list(map(int,input().split()))
count = 0
now = 1
city = [1]
city2 = {1}
while count < K:
    count +=  1
    now = A[now-1]
    if now in city2:
        break
    else:
        city.append(now)
        city2.add(now)
if count == K:
    print(now)
else:
    n = city.index(now)
    K -= n
    count -= n
    K %= count
    print(city[n+K])

Submission status: Accepted

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

now = 1

while K:
  if K & 1:
    now = A[now]
  A = [A[A[i]] for i in range(len(A))]
  K >>= 1
  
print(now)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
list = []
replist = []
judge = [True] * (2 * 10 ** 5 + 1)
pos = 1
owari = True
while owari:
    judge[pos] = False
    list.append(pos)
    pos = A[pos]
    if not judge[pos]:
        while True:
            replist.append(pos)
            judge[pos] = True
            pos = A[pos]
            if judge[pos]:
                owari = False
                break
if K <= len(list)-1:
    print(list[K])
else:
    K = K - len(list) + 1
    print(replist[( K % len(replist) ) -1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    n, k, *a = map(int, read().split())

    cur = 1
    path = [0] * (n + 1)
    while k:
        if path[cur]:
            break
        else:
            path[cur] = k
            cur = a[cur - 1]
            k -= 1
            if k == 0:
                print(cur)
                sys.exit()
    cycle = path[cur] - k
    k = k % cycle
    while k:
        cur = a[cur - 1]
        k -= 1
    print(cur)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a = [_ - 1 for _ in a]

history = []
last_visited = [None for i in range(n)]
now = 0

history.append(0)
last_visited[0] = 0

for t in range(1, k+1): # 1, 2, ..., k
  now = a[now]
  history.append(now)
  
  if last_visited[now] is None:
    last_visited[now] = t
    if t == k:
      print(now + 1)
      sys.exit()
  else:
    t0 = last_visited[now]
    t1 = t
    # 頂点 now に t0 及び t1 に訪問した状況
    # 等差数列 S = [t0, t1, .....] を考えて，
    # 「k 以下の最大の S の要素」t_max を求める
    t_max_idx = (k - t0) // (t1 - t0)
    t_max = t0 + (t1 - t0) * t_max_idx
    
    # 時刻 t_max に history[t0] にいる
    # → 時刻 k には history[t0 + (k - t_max)] にいる
    print(history[t0 + (k - t_max)] + 1)
    sys.exit()

Submission status: Accepted

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = list(map(int,stdin.readline().split()))
for i in range(n):
    a[i] -= 1
d = {}
d[0] = k
cur = 0
while k > 0:
    cur = a[cur]
    k -= 1
    if cur in d:
        looplen = d[cur] - k
        k %= looplen
    else:
        d[cur] = k
print(cur + 1)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    inlis = list(map(int, input().split()))
    flag = 0
    trans = 0
    now = 1
    indic = dict()
    indic[1] = 0

    while flag < 1:
        if trans < k:
            trans += 1
            tsugi = inlis[now-1]
            now = tsugi
            if tsugi not in indic:
                indic[tsugi] = trans
                #print(tsugi, indic)
            else:
                flag = 1
                loop = trans - indic[tsugi]
                yokei = indic[tsugi]
                #print(loop, yokei)

        if trans == k:
            print(tsugi)
            exit()
    
    loopamari = (k-yokei) % loop

    for _ in range(loopamari):
        tsugi = inlis[now-1]
        now = tsugi
    
    print(now)
    




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = list(map(int,stdin.readline().split()))
for i in range(n):
    a[i] -= 1
d = {}
d[0] = 0
cur = 0
step = 0
while step < k:
    cur = a[cur]
    step += 1
    if cur in d:
        looplen = step - d[cur]
        step += looplen * ((k-step)//looplen)
    else:
        d[cur] = step
print(cur + 1)

Submission status: Accepted

Solution code:
from sys import stdin
import math
n,k = map(int,stdin.readline().split())
a = list(map(int,stdin.readline().split()))
d = math.floor(math.log2(k))
next = [[-1 for _ in range(n)] for _ in range(d+1)]
for i in range(n):
    next[0][i] = a[i] - 1
for j in range(d):
    for i in range(n):
        if next[j][i] == -1:
            continue
        next[j+1][i] = next[j][next[j][i]]
cur = 0
i = 0
while k > 0:
    if k&1:
        cur = next[i][cur]
    k >>= 1
    i += 1
print(cur+1)

Submission status: Accepted

Solution code:
from copy import deepcopy

def main():
    n, k = map(int, input().split())
    a = [int(x)-1 for x in input().split()]
    visited = set()
    i = 0
    cnt = 0
    # 途中で前に行ったところに行ったら終わり
    # kが小さくてcnt == kになってもおわり
    while True:
        if i in visited:
            break
        visited.add(i)
        cnt += 1
        i = a[i]
        if cnt == k:
            print(i+1)
            exit()
    k -= cnt
    period = list()
    period.append(i)
    i = a[i]
    # 何回で同じ場所に戻るか
    while True:
        if i == period[0]:
            break
        period.append(i)
        i = a[i]
    # 余り
    mod = k % len(period)
    ans = period[mod]
    print(ans+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
259
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
m=1
towns=[1]
flg=[0]*(N+1)
flg[1]=1
while 1:
    m=A[m]
    towns.append(m)
    if flg[m]==1:
        l=len(towns)-towns.index(m)-1
        break
    flg[m]=1
pl=towns.index(m)
if K<=pl:
    print(towns[K])
else:
    print(towns[(K-pl)%l+pl])

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
b=[False]*n
pos=0
for i in range(min(n,k)):
    if b[pos]!=False:
        loop=i-b[pos]+1
        break
    b[pos]=i+1
    pos=a[pos]-1
    k-=1
if k>0:
    for i in range(k%loop):
        pos=a[pos]-1
print(pos+1)

Submission status: Accepted

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

tt = [0] * n
tt[0] = 1
ans_l = [1]
i = 1
c = 0

while True:
    if c == k: #ループに達することができないk回を入力として与えられるとこの条件式がない場合
        break  #ループに達した上で計算されてしまう。これがあるとkが下の式で0として計算される。
    c += 1
    i = a[i-1]
    if tt[i-1] == False:
        tt[i-1] = 1
        ans_l.append(i)
    else:
        break

#print(c,k)
d = ans_l.index(i)
k -= d
ans = k % (len(ans_l)-d)
print(ans_l[ans+d])

Submission status: Accepted

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

tt = [0] * n
tt[0] = 1
ans_l = [1]
i = 1
c = 0

while True:
    if c == k:
        break
    c += 1
    i = a[i-1]
    if tt[i-1] == False:
        tt[i-1] = 1
        ans_l.append(i)
    else:
        break

d = ans_l.index(i)
k -= d
ans = k % (len(ans_l)-d)
print(ans_l[ans+d])

Submission status: Accepted

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

tt = [0] * n
tt[0] = 1
ans_l = [1]
i = 1

for j in range(k):
    i = a[i-1]
    if tt[i-1] == False:
        tt[i-1] = 1
        ans_l.append(i)
    else:
        break

d = ans_l.index(i)
k -= d
ans = k % (len(ans_l)-d)
print(ans_l[ans+d])

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())

    # ダブリング
    d = 60
    to = [[0 for _ in range(n)]
          for _ in range(d)]  # to[i][j] : 町jから2**i回ワープした町
    to[0] = list(map(int, input().split()))

    for i in range(1, d):
        for j in range(n):
            to[i][j] = to[i - 1][to[i - 1][j] - 1]

    v = 1
    for i in range(d, -1, -1):
        l = 2 ** i  # 2**i回ワープする

        if l <= k:
            v = to[i][v - 1]
            k -= l

        if k == 0:
            break

    print(v)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

num = 1
li = [1]
flag = [True] * n
flag[0] = False

for i in range(k):
    num = a[num-1]
    if flag[num-1]:
        li.append(num)
        flag[num-1] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d

print(li[ans])

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    visited_list = [0] + [-1] * (n - 1)  # 何ワープ目で訪れたか
    path_list = [1]  # 訪れた街の順番
    city, loop, non_loop = 1, 0, 0  # 今いる街、何ワープでループするか、最初にループするまでのワープ数

    for i in range(1, n + 1):
        city = a_list[city - 1]
        if visited_list[city - 1] != -1:
            loop = i - visited_list[city - 1]
            non_loop = visited_list[city - 1]
            break
        else:
            visited_list[city - 1] = i
            path_list.append(city)

    city = 1
    if k <= non_loop:
        city = path_list[k]
    else:
        city = path_list[non_loop + (k - non_loop) % loop]

    print(city)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    visited_list = [-1] * n  # 何ワープ目で訪れたか
    visited_list[0] = 0
    path_list = [1]
    city, loop, non_loop = 1, 0, 0  # 今いる街、何ワープでループするか、最初にループするまでのワープ数

    for i in range(1, n + 1):
        city = a_list[city - 1]
        path_list.append(city)
        if visited_list[city - 1] != -1:
            loop = i - visited_list[city - 1]
            non_loop = visited_list[city - 1]
            break
        else:
            visited_list[city - 1] = i

    city = 1
    if k <= non_loop:
        city = path_list[k]
    else:
        city = path_list[non_loop + (k - non_loop) % loop]

    print(city)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    visited_list = [-1] * n  # 何ワープ目で訪れたか
    visited_list[0] = 0
    city, loop, non_loop = 1, 0, 0  # 今いる街、何ワープでループするか、最初にループするまでのワープ数

    for i in range(1, n + 1):
        city = a_list[city - 1]
        if visited_list[city - 1] != -1:
            loop = i - visited_list[city - 1]
            non_loop = visited_list[city - 1] - 1
            break
        else:
            visited_list[city - 1] = i

    city = 1
    if k <= non_loop:
        for _ in range(k):
            city = a_list[city - 1]
    else:
        for _ in range(non_loop + (k - non_loop) % loop + loop):
            city = a_list[city - 1]

    print(city)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

done = [-1]*N
done[0] = 0

tmp = 0
done[0] = 0
for k in range(1, K + 1):
    tmp = A[tmp]
    if done[tmp] >= 0:
        for _ in range((K - done[tmp]) % (k - done[tmp])):
            tmp = A[tmp]
        print(tmp + 1)
        exit()
    else:
        done[tmp] = k
print(tmp + 1)

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)


def dfs(v):
    path.append(v)
    visited[v] = 1
    nv = A[v]
    if visited[nv] == 1:
        return nv
    return dfs(nv)


N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
visited = [0] * N
path = []
cycle_start = dfs(0)
cycle_len = len(path) - path.index(cycle_start)
head_len = len(path) - cycle_len
if K <= head_len:
    print(path[K] + 1)
else:
    K -= head_len
    print(path[head_len + K % cycle_len] + 1)

Submission status: Accepted

Solution code:
#  #16586869
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
now = 1
check = [-1]*(n+1)
for i in range(k):
  if check[now] == -1:
    check[now] = i
    now = a[now]
  else:
    loop = i - check[now] # check?
    afterloop = (k-(i-loop))%loop
    print(check.index((i-loop)+afterloop))
    exit()
print(now)

Submission status: Accepted

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

now = 1
check = [-1]*(n+1)

for i in range(k):
  if check[now] == -1:
    check[now] = i
    now = a[now]
  else:
    loop = i - check[now]
    afterloop = (k-(i-loop))%loop
    print(check.index((i-loop) + afterloop))
    exit()
print(now)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
hist = [0 for _ in range(N+1)]
hist[1] = 1
cur = A[1]
while True:
    cur = A[cur]
    if hist[cur]==0:
        hist[cur]=1
    else:break
s = cur
cur = A[s]
T = 1
while cur!=s:
    cur = A[cur]
    T += 1
T1 = 0
cur = 1
while cur!=s:
    cur = A[cur]
    T1 += 1
if K<=T1:
    cur = 1
    cnt = 0
    while cnt<K:
        cur = A[cur]
        cnt += 1
    print(cur)
else:
    K = (K-T1)%T
    cur = s
    cnt = 0
    while cnt<K:
        cur = A[cur]
        cnt += 1
    print(cur)

Submission status: Accepted

Solution code:
from sys import exit
n, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
done = [-1 for _ in range(n)]
tmp = 0
done[0] = 0
for k in range(1, K + 1):
    tmp = A[tmp]
    if done[tmp] >= 0:
        for i in range((K - done[tmp]) % (k - done[tmp])):
            tmp = A[tmp]
        print(tmp + 1)
        exit()
    else:
        done[tmp] = k
print(tmp + 1)

Submission status: Accepted

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

tel = [[0] * n for _ in range(63)]
tel[0] = a
for i in range(62):
    for j in range(n):
        tel[i + 1][j] = tel[i][tel[i][j]]

now = 0
for i in range(62, -1, -1):
    if k >> i & 1:
        now = tel[i][now]
print(now + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*(n+1)
count=0
now=1
f=1
for _ in range(k):
    if b[now]:
        f=0
        break
    count+=1
    b[now]=count
    now=a[now-1]
if f:
    print(now)
    exit()
x=count-b[now]+1
y=(k-b[now]+1)%x
for i in range(y):
    now=a[now-1]
print(now)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
warp = list(map(int, input().split()))
warp = [i - 1 for i in warp]

visit = [0]

current_loc = 0
while warp[current_loc] != -1:
  visit.append(warp[current_loc])
  warp[current_loc] = -1
  current_loc = visit[-1]

res = visit.index(visit[-1])
cycle = visit[res + 1:]
if K <= res:
  print(visit[K] + 1)
else:
  answer = cycle[(K - res - 1) % (len(visit) - 1 - res)] + 1
  print(answer)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
rec = [0]
i = 0
flag = [0 for _ in range(n + 1)]
while True:
    if flag[rec[i]] == 0:
        flag[rec[i]] = 1
        rec.append(a[rec[i]] - 1)
    else:
        start = rec.index(a[rec[i]] - 1)
        loop = rec[start:]
        pre = rec[:start]
        break
    i += 1
count = (k - len(pre)) % len(loop)
if k <= len(pre):
    print(pre[k] + 1)
else:
    print(loop[count] + 1)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))
l = [0]*n
i=0
cnt=0
while l[i]==0:
    l[i] = a[i]
    i = a[i]-1 
    cnt += 1
start = i+1
i = 0
pre = 0
while i+1!=start:
    i = a[i]-1
    pre += 1
loop = cnt-pre
if pre+loop<k:
    k=(k-pre)%loop+pre
i = 0
for _ in range(k):
    i = a[i]-1
print(i+1)

Submission status: Accepted

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

now = 1
path = [1]

for i in range(N + 2):
    now = A[now]
    path.append(now)

if i >= K:
    print(path[K])
    quit()

now = path.pop()
lo_start = i - 1
while path[lo_start] != now:
    lo_start -= 1

loop = path[lo_start:]

ans = loop[(K - path.index(now)) % len(loop)]

print(ans)

Submission status: Accepted

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

cnts = [None] * N

pos = 0
cnt = 0

while cnt < K:
    if cnts[pos] != None:
        loop_size = cnt - cnts[pos]
        cnt += ((K-cnt-1) // loop_size) * loop_size
        cnts = [None] * N
    cnts[pos] = cnt
    pos = A[pos]
    cnt += 1

print(pos+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 18:05:47 2020

@author: liang
"""

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
visited = [-1]*N
loop = list()

cur = 1
cnt = 0
while visited[cur-1] == -1:
#while True:
    visited[cur-1] = cnt
    loop.append(cur)
    cnt += 1
    cur = A[cur-1]
    if cnt == K:
        print(cur)
        #print(loop)
        break
else:
    #print(loop)
    loop = loop[visited[cur-1]:]
    T = cnt -visited[cur-1]
    #print(loop, T)
    ans = loop[(K - cnt)%T]
    print(ans)

Submission status: Accepted

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

kyori = [-1] *len(A)

junban =[]

x=0
d=0
while kyori[x] == -1:
    
    junban.append(x)
    kyori[x]=d
    d+=1
    x=A[x]-1
    
    
roop_x = x
roop_d = d - kyori[x]

# for k in range(100):

if k<d:
    print(junban[k]+1)
    
else:
    
    k0 = kyori[x]
    k1 = (k-k0)%roop_d
    
    print(junban[k0+k1]+1)

Submission status: Accepted

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

check = [0] * (N+1) #対象の町を訪問するのが初めてか
li = [] #町の移動順
i, j = 1, 1 #現在の町の番号と移動回数

while True:
  k = A[i-1] #移動先の町の番号
  if check[k] == 1:
    #前に訪問したことがある場合
    n = li.index(k)+1 #ループに入った時点での移動回数
    break
  check[k] = 1
  li.append(k)
  i = k
  j += 1

if K < n: print(li[K-1])
else: print(li[(K-n) % (j-n) + n - 1])

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
check = [0]*N
ima = 0

for i in range(K):
  if check[A[ima]-1] != 0:
    loopen = ima
    check[ima] = i+1
    looplen = check[ima] - check[A[ima]-1] + 1
    loopend = i
    break
  if i == K-1:
    print(A[ima])
    exit()
  check[ima] = i+1
  ima = A[ima]-1

offset = (K-(i-looplen)-1)%looplen
ima = 0
for i in range(loopend-looplen+offset+1):
  ima = A[ima]-1
print(ima+1)

Submission status: Accepted

Solution code:
def main():
    N,K = map(int,input().split())
    A = [0] + list(map(int,input().split()))
    
    i = 1
    pas = [i]
    pas_set = set(pas)
    k = 1
    while k <= K:
        if A[i] in pas_set:
            rps = pas.index(A[i])
            ans = A[i]
            break
        pas.append(A[i])
        pas_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps)%(k-rps)
        print(pas[rps+rpnum])

main()

Submission status: Accepted

Solution code:
import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    i = 1
    pas = np.zeros(N)
    pas[0] = i
    k = 1
    pass_set = set(pas)
    while k <= K:
        if A[i] in pass_set:
            rps = np.where(pas==(A[i]))[0]
            ans = A[i]
            break
        pas[k] = A[i]
        pass_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))

main()

Submission status: Accepted

Solution code:
from collections import deque
n, k = map(int, input().split())
a = [-1] + list(map(int, input().split()))
town = [-1] * (n + 1)
town[1] = 0
now_town = 1
second_first = 0
while True:
    if town[a[now_town]] != -1:
        second_first = a[now_town]
        break
    town[a[now_town]] = town[now_town] + 1
    if town[a[now_town]] == k:
        print(a[now_town])
        exit()
    now_town = a[now_town]
    # print(town)
start_index = town[second_first]
end_index = max(town)
rest = k - end_index
div = (rest-1) % (end_index - start_index + 1)
# print(rest, div)
ans = town.index((start_index) + div)
print(ans)

Submission status: Accepted

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

tele = [1]
went = set(tele)
now = 1
cnt = 0
flag = True

for i in range(k):
  now = a[now-1]
  if i != k-1 and now in went:
    tele = tele[tele.index(now):]
    cnt = i+1
    flag = False
    break
  tele.append(now)
  went.add(now)

if flag == True:
  print(tele[-1])

else:
  k -= cnt
  cnt = k % len(tele)
  print(tele[cnt])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(lambda x:int(x)-1,input().split()))
i = 0
visited = set([0])

while K > 0:
    i = A[i]
    K -= 1
    if i in visited:
        break
    visited.add(i)
if K == 0:
    print(i+1)
    exit(0)
ls = [i]
j = i
while True:
    j = A[j]
    if j == i:
        break
    ls.append(j)
print(ls[K % len(ls)]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = 0
res = [-1] * 3*10**5
d = 0
way = []
l = 0
c = 0

for i in range(N) :
    A[i] -= 1
    
for i in range(K+1):
    if(res[pos] != -1) :
        l = d - res[pos]
        c = d - l
        res[pos] = d
        break
    res[pos] = d
    way.append(pos)
    d += 1
    pos = A[pos]

ans = 0
if(K+1 <= len(way)) :
    ans = way[K]
else :
    K -= c
    K = K%l
    ans = way[K + c]
print(ans+1)

Submission status: Accepted

Solution code:
def delete_head_zeros(n):
	n = str(n)
	l = len(n)
	if "." in n:
		l = n.find(".")
	head_zeros = 0
	for i in range(l - 1):
		if n[i] == "0":
			head_zeros += 1
		else:
			break

	return n[head_zeros:]

# compare a, b
# a, b: int or string
def bigint_compare(a, b):
	a = delete_head_zeros(a)
	b = delete_head_zeros(b)
	if len(a) > len(b):
		return 1
	elif len(a) < len(b):
		return -1
	else:
		if a > b:
			return 1
		elif a < b:
			return -1
		else:
			return 0

# calculate a + b
# a, b: int or string
def bigint_plus(a, b):
	a = str(a)
	b = str(b)

	d = max([len(a), len(b)])
	a = '0' * (d - len(a)) + a
	b = '0' * (d - len(b)) + b

	ans = ""
	carry = 0
	for i in range(d):
		s = int(a[-i-1]) + int(b[-i-1]) + carry
		carry = s // 10
		ans = str(s % 10) + ans
	else:
		if carry:
			ans = str(carry) + ans

	return ans

# calculate a - b
# a, b: int or string
def bigint_minus(a, b): 
	a = str(a)
	b = str(b)
	M = []
	m = []
	sign = ""

	if len(a) > len(b) or (len(a) == len(b) and a >= b):
		[M, m] = [a, b]
	else:
		[M, m] = [b, a]
		sign = "-"
	m = '0' * (len(M) - len(m)) + m

	ans = ""
	borrow = 0
	for i in range(len(M)):
		s = int(M[-i-1]) - int(m[-i-1]) - borrow
		if s < 0:
			borrow = 1
			s += 10
		else:
			borrow = 0
		ans = str(s) + ans

	return sign + delete_head_zeros(ans)

# calculate a * b
# a, b: int or string
def bigint_multiply(a, b):
	a = str(a)
	b = str(b)

	md = []
	for j in range(len(b)):
		carry = 0
		mj = ""
		for i in range(len(a)):
			m = int(a[-i-1]) * int(b[-j-1]) + carry
			carry = m // 10
			mj = str(m % 10) + mj
		else:
			if carry:
				mj = str(carry) + mj
		md.append(mj)

	ans = 0
	for k in range(len(md)):
		ans = bigint_plus(md[k] + "0" * k, ans)

	return ans


# calculate a / b to d digits after decimal point
# a, b, d: int or string
def bigint_divide(a, b, d = 0):
	a = str(a)
	b = str(b)
	d = int(d)
	if d < 0:
		d = 0

	ans = ""
	r = ""
	for i in range(len(a) + d):
		q = 0
		if i < len(a):
			r += a[i]
		elif i == len(a):
			ans += "."
			r += "0"
		else:
			r += "0"

		if bigint_compare(r, b) == -1:
			ans += str(q)
		else:
			while bigint_compare(r, b) >= 0:
				r = bigint_minus(r, b)
				q += 1
			ans += str(q)

	return delete_head_zeros(ans)

def main():
	N, K = input().split(" ")
	A = [int(a) - 1 for a in input().split(" ")]
	visited = [0] * int(N)
	towns = []
	now = 0
	while visited[now] == 0:
		towns.append(now)
		visited[now] = 1
		now = A[now]
	else:
		loop_begin_idx = towns.index(now)
		loop_end_idx = len(towns) - 1
		loop_n = loop_end_idx - loop_begin_idx + 1
	if int(K) < len(towns):
		print(towns[int(K)] + 1)
		return 0
	K_from_loop = bigint_minus(K, loop_begin_idx)
	q = bigint_divide(K_from_loop, loop_n)
	r = bigint_minus(K_from_loop, bigint_multiply(loop_n, q))
	print(towns[loop_begin_idx + int(r)] + 1)

main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,k = LI()
    a = [None] + LI()
    explored = {1}
    lst = [1]
    lenth = 0
    start = 0
    junkan = []
    now = 1
    while lenth==0:
        nxt = a[now]
        if nxt in explored:
            index = lst.index(nxt)
            junkan = [lst[-1]] + lst[index:-1]
            start = index
            lenth = len(junkan)
        else:
            explored.add(nxt)
            lst.append(nxt)
        now = nxt
    ans = 0
    if k<start:
        ans = lst[k]
    else:
        r = (k-start+1)%lenth
        ans = junkan[r]

    print(ans)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain


def solve(N: int, K: int, A: "List[int]"):
    M = [-1 for _ in range(N)]
    M[0] = 0
    current = 1
    n = 1
    while n <= K:
        current = A[current - 1]
        if M[current - 1] == -1:  # 一度も通ったことがない
            M[current - 1] = n  # n ステップ目に通った事を記録
        else:
            loop_len = n - M[current - 1]  # ループの長さ
            rest = K - n  # 残り長さ
            rest = rest % loop_len  # 残り長さをループの余剰にする
            K = n + rest
        n += 1
    return current


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # N, K, A = map(int, line.split())
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, K, A)
    print(answer)


if __name__ == "__main__":
    main()