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:
def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] + A

    seen = {}
    find_cnt = {}
    cnt = 0
    dst = 1
    while K:
        if dst in seen:
            cycle = cnt - seen[dst]
            K %= cycle
            print(find_cnt[seen[dst]+K])
            return

        else:
            seen[dst] = cnt
            find_cnt[cnt] = dst

        dst = A[dst]
        cnt += 1
        K -= 1

    print(dst)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ai = list(map(int, input().split()))
for i in range(N):
    ai[i] -= 1
    
import math
dv = []
dv.append(ai)
for k in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        
#a = []
now = 0
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        #a.append(i)
        now = dv[i][now]
print(now + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
ai = list(map(int, input().split()))
for i in range(N):
    ai[i] -= 1
    
import math
dv = []
dv.append(ai)
for k in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        
a = []
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        a.append(i)
        
now = 0
for i in a:
    now = dv[i][now]
print(now + 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

tmp = [0 for i in range(n + 1)]
cnt = 0
res = 1

while cnt < k:
    cnt += 1
    if tmp[res] == 0:
        tmp[res] = cnt
    else:
        cnt += (k - cnt) // (cnt - tmp[res]) * (cnt - tmp[res])
        tmp[res] = cnt
    res = A[res - 1]

print(res)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
an = list(map(int, input().split()))
for i in range(n):
    an[i] -= 1
    
import math
dv = []
dv.append(an)
K = k
N = n
for _ in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)

for k in range(1, int(math.log2(K)) + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        
# N 回目を 2 ^ t で表すためにビット演算を用いる
# a : dv の何行目を用いるかを格納
a = []
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        a.append(i)
        
now = 0
for i in a:
    now = dv[i][now]
        
print(now + 1)

Submission status: Accepted

Solution code:
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
town=set()
town.add(1)
town_ls=[1]
now=1
for i in range(min([K,N])):
  now=ls[now-1]
  if now in town:
    break
  town.add(now)
  town_ls.append(now)

if i+1==K:
  print(now)
else:
  L=i+1
  S=town_ls.index(now)
  loop=L-S
  #print(loop,S)
  x=(K-S)%loop+S
  print(town_ls[x])

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
a=lnii()

x=0
x_list=[1]
x_table=[0 for i in range(n+1)]
x_table[1]=1

for i in range(k):
  nx=a[x]

  if x_table[nx]!=0:
    inx=x_list.index(nx)
    loop=x_list[inx:]
    zan=k-i

    q=zan%len(loop)

    nx=loop[q-1]
    break

  else:
    x=nx-1
    x_list.append(nx)
    x_table[nx]+=1

print(nx)

Submission status: Accepted

Solution code:

url = "https://atcoder.jp/contests/abc162/tasks/abc162_d"
import itertools


def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    route = []
    istuka = [0] * (n+1)
    next = 1
    # 同じ街に訪れるまでループ
    for _ in range(k):
        if istuka[next] == 1:
            break
        else:
            istuka[next] = 1
            route.append(next)
        next = a[next - 1]
    if n >= k:
        print(next)
        exit()
    ans = route[route.index(next):]
    idx = (k - route.index(next)) % len(ans)
    print(ans[idx])



if __name__ == '__main__':
    main()

Submission status: Accepted

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

path = [0]*(N+1)
visited = set()

pos = 1
for i in range(N+1):
    if pos in visited: break
    path[i] = pos
    visited.add(pos)
    pos = A[pos]

loc = path.index(pos)
head = path[:loc]
rep = path[loc:i]

if K < len(head):
    print(head[K])
else:
    print(rep[(K - len(head)) % len(rep)])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
data=[0]*(n+1)
data[1]=1
ans=[1]
res=0
for i in range(n):
  p=a[res]
  if data[p]==0:
    data[p]=1
    ans.append(p)
    res=p-1
  else:
    res=ans.index(p)
    break
if len(ans)>k:
  print(ans[k])
else:
  m=len(ans)-res
  k-=res
  d=k%m
  print(ans[res+d])

Submission status: Accepted

Solution code:
#nは街の数　kは移動の回数　k＋１個の街にいくことになる　
#最高でもn回移動すれば一つは二回訪れる街が現れる　そのあとはループする
n,k = map(int,input().split())
a = list(map(int,input().split()))

b = [-1]*(n+1) #街３に5回目の移動でついた場合、b[3]に５が入る　
tmp = [] #経路を記録していく
here = 1
count = 0 #移動回数

while True:
    if b[here] != -1: #一度訪れた街に再び来た
        roop = count - b[here] #ループの長さ　(街aに二回目に来た時の移動回数-一回目に来た時の移動回数)
        if k < count: #ループに入る前に移動が終わった時
            print(tmp[k])
        else:
            new_tmp = tmp[b[here]:]
            s = k-b[here]
            print(new_tmp[s%roop])
        break
    b[here] = count
    count += 1
    tmp.append(here)
    here = a[here-1]

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for i in range(1, n+1):
    d[i] = 0
l = [1]
x = 1
if n >= k:
    for i in range(k):
        x = a[x-1]
    print(x)
    exit()
for i in range(n):
    x = a[x-1]
    if d[x] == 1:
        k -= l.index(x)
        print(l[l.index(x):][k%(l.index(x)-len(l))])
        exit()
    l.append(x)
    d[x] += 1
print(x)

Submission status: Accepted

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

timestep_pos_map = []  # (i -> n)
pos_timestep_map = {}  # (n -> i)

timestep_pos_map.append(1)  # start
pos_timestep_map[1] = 0     # start

for timestep in range(1, min(K + 1, N + 1 + 1)):
    prev_pos = timestep_pos_map[-1]
    cur_pos = A[prev_pos - 1]

    if timestep == K:
        print(cur_pos)
        exit()

    if cur_pos in pos_timestep_map:
        prev_timestep = pos_timestep_map[cur_pos]
        interval = timestep - prev_timestep
        offset = (K - prev_timestep) % interval
        print(timestep_pos_map[prev_timestep + offset])
        exit()

    timestep_pos_map.append(cur_pos)
    pos_timestep_map[cur_pos] = timestep

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
c = 0
List = []
check = [-1]*N
tmp = 1
for i in range(min(N+1,K)):
    tmp2 = A[tmp-1]
    List.append(tmp2)
    if(check[tmp2-1] >= 0):
        tmp3 = check[tmp2-1]
        del List[-1]
        break
    else:
        check[tmp2-1] = i
        tmp = tmp2
        c += 1
if(c >= K):
    print(List[K-1])
else:
    List2 = List[tmp3:]
    if(c == len(List2)):
        print(List2[(K%len(List2))-1])
    else:
        K -= c
        print(List2[(K%len(List2))-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
k-=p
loop=len(w)-p
print(w[p+k%loop])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
if p==0:
    print(w[k%len(w)])
else:#l 2,5,3
    p=w.index(t)
    k-=p
    loop=len(w)-p
    print(w[p+k%loop])

Submission status: Accepted

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

import numpy as np


# def input():
#     return sys.stdin.readline().rstrip()


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

    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        # dp[h] = dp[h - 1][dp[h - 1]]
        dp[h] = np.take(dp[h - 1], dp[h - 1])

    node = 1
    # for i in reversed(range(k.bit_length())):
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Submission status: Accepted

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


d = [[-1] * n for _ in range(70)]

for i in range(n):
    d[0][i] = a[i] - 1

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

dst = 0
while k:
    i = 70
    while pow(2, i) & k <= 0:
        i -= 1

    dst = d[i][dst]
    k -= pow(2, i)

print(dst + 1)

Submission status: Accepted

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

id = [-1] * (N + 1)
x = 1
l = 0
a = []
while id[x] == -1:
    a.append(x)
    id[x] = l
    l += 1
    x = A[x]

c = l - id[x]
if K < l:
    print(a[K])
else:
    K -= l
    print(a[id[x] + K % c])

Submission status: Accepted

Solution code:
if __name__ == '__main__':

    n,k = map(int,input().split())
    A = [0]
    AA= list(map(int,input().split()))
    A = A + AA

    B = set()
    cnt = 0
    ind = 1
    startind = 0
    D = []
    while True:
        if A[ind] not in B:
            B.add(ind)
            D.append(ind)
            cnt += 1
            ind = A[ind]
        else:
            B.add(ind)
            D.append(ind)
            cnt += 1
            startind = A[ind]
            break

    C = set()
    ind = startind
    ANS = []
    while True:
        if A[ind] not in C:
            C.add(ind)
            ind = A[ind]
            ANS.append(ind)
        else:
            C.add(ind)
            ANS.append(A[ind])
            break

    if k >= cnt:
        tmp = k - cnt
        tmp = tmp % (len(C))
        print(ANS[tmp-1])
    else:
        print(D[k])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
B[0]=1
if B[0] in A:c=B[0]
for i in range(1,N):
  B[i]=A[B[i-1]-1]

d=B.index(B[-1])+1
if K<=N:print(B[K]);exit()
print(B[d-1+(K+1-d)%(N-d)])

Submission status: Accepted

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

d=B.index(B[-1])+1
if K<=N:print(B[K]);exit()
print(B[d-1+(K+1-d)%(N+1-d)])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
B[0]=1;c=0;d=0
if B[0] in A:c=B[0]
for i in range(1,N+1):
  B[i]=A[B[i-1]-1]

d=B.index(B[-1])+1
if K<=N:print(B[K]);exit()
#if (K+1-d)%(N+1-d)==0:print(B[-1])
print(B[d-1+(K+1-d)%(N+1-d)])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
B[0]=1;c=0;d=0
if B[0] in A:c=B[0]
for i in range(1,N+1):
  B[i]=A[B[i-1]-1]
#  if c==B[i]:break
#  if A.count(B[i])>1 and d==0:c=B[i];d+=1

d=B.index(B[-1])+1
#print(B.index(B[N-1]))

#print(B,d)
#print(d+1+(K-d-1)%(N-d-1))
#print(B[K],K,d,(K+1-d),(N+1-d))
if K<=N:print(B[K]);exit()
if (K+1-d)%(N+1-d)==0:print(B[-1])
else:print(B[d-1+(K+1-d)%(N+1-d)])
#print(B[d+1+(K-d-1)%(N-d-1)]-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = [-1] + list(map(int, input().split()))

I = [-1] * (N + 1)
S = []
idx = 1
while I[idx] == -1:
    S.append(idx)
    I[idx] = len(S)
    idx = A[idx]
# print(f'{S=}, {idx=}, {I[idx]=}')

start_idx = I[idx] - 1
num_circles = len(S) - start_idx
# print(f'{start_idx=}, {num_circles=}')

if K < len(S) - 1:
    ans = S[K]
else:
    K -= start_idx
    div, mod = divmod(K, num_circles)
    ans = S[start_idx + mod]
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
Alist=list(map(int,input().split()))
already=[1]
alreadyset={1}
last=1
while True:
    if Alist[last-1] in alreadyset:
        start=already.index(Alist[last-1])
        break
    already.append(Alist[last-1])
    alreadyset.add(Alist[last-1])
    last=Alist[last-1]
roop=len(already)-start
if K-len(already)<0:
    print(already[K])
else:
    index=(K-start)%roop+start
    while not start<=index<len(already):
        index=index%roop+start
    print(already[index])

Submission status: Accepted

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

import numpy as np


# def input():
#     return sys.stdin.readline().rstrip()


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

    warps = list(map(int, input().split()))
    warps = [0] + warps
    # warps = np.array(warps, dtype=int)

    # order_num = np.zeros(len(warps) + 1, dtype=int)
    order_num = [0 for i in range(len(warps))]
    path_history = []

    node = 1
    while order_num[node] == 0:
        path_history.append(node)
        order_num[node] = len(path_history)
        node = warps[node]

    # print(order_num)
    # print(path_history)
    begin = order_num[node]
    # print(tail)

    if k <= begin:
        print(path_history[k])
    else:
        # path_history = path_history[tail:]
        # print(path_history)
        leng = len(path_history) - order_num[node] + 1
        # print(leng)
        index = (k - (begin - 1)) % leng
        # print(index)
        print(path_history[begin - 1 + index])


main()

Submission status: Accepted

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

import numpy as np


# def input():
#     return sys.stdin.readline().rstrip()


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

    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    order_num = np.zeros(len(warps) + 1, dtype=int)
    path_history = []

    node = 1
    while order_num[node] == 0:
        path_history.append(node)
        order_num[node] = len(path_history)
        node = warps[node]

    # print(order_num)
    # print(path_history)
    begin = order_num[node]
    # print(tail)

    if k <= begin:
        print(path_history[k])
    else:
        # path_history = path_history[tail:]
        # print(path_history)
        leng = len(path_history) - order_num[node] + 1
        # print(leng)
        index = (k - (begin - 1)) % leng
        # print(index)
        print(path_history[begin - 1 + index])


main()

Submission status: Accepted

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

import sys
import numpy as np


# def input():
#     return sys.stdin.readline().rstrip()


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

    # warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    # for i in reversed(range(k.bit_length())):
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Submission status: Accepted

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

import sys
import numpy as np


def input():
    return sys.stdin.readline().rstrip()


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

    # warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    # for i in reversed(range(k.bit_length())):
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Submission status: Accepted

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

import sys
import numpy as np


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

    warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    # for i in reversed(range(k.bit_length())):
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Submission status: Accepted

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

import sys
import numpy as np


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

    warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    # for i in reversed(range(k.bit_length())):
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Submission status: Accepted

Solution code:
from math import log2

n,k = map(int, input().split())
al = list(map(int, input().split()))

logk = int(log2(k))+1
db = [ [0]*n for _ in range(logk) ]
for ni in range(n): 
    db[0][ni] = al[ni]-1
for ki in range(logk-1):
    for ni in range(n):
        db[ki+1][ni] = db[ki][db[ki][ni]]

now = 0
for i in range(logk):
    if k&(1<<i) > 0:
        now = db[i][now]
print(now+1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
doubling = [[0]*N for _ in range(61)]
doubling[0] = list(map(lambda x:x-1, As))

for i in range(1, 61):
    for j in range(N):
        doubling[i][j] = doubling[i-1][doubling[i-1][j]]

now = 0
for i in range(61):
    if (K>>i)&1:
        now = doubling[i][now]
print(now+1)

Submission status: Accepted

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

count = 0

stack = set()
visited = []
visited_set = set()
endf = False

current = 0
while True:
    i = A[current]-1
    visited_set.add(current)
    visited.append(current)

    if not i in visited_set:
        current = i
        count += 1
    else:
        leng = len(visited_set)
        roop_len = leng - visited.index(i)
        header_len = leng - roop_len
        break

    if count >= K:
        endf = True
        print(i+1)
        break

if not endf:
    roop_ind = (K - header_len + 1) % roop_len
    if roop_ind == 0:
        print(visited[-1]+1)
    else:
        print(visited[header_len + roop_ind-1]+1)

Submission status: Accepted

Solution code:
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    P = [p]
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
        P.append(p)
    front = P[:L]
    if L != N:
        cycle, end = P[L:R], P[L:L+(N-L)%period]
        cnt = (N-L)//period
    return front, cycle, end, cnt

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


import sys
input = sys.stdin.readline

def lift(x): return A[x-1]

N, K = map(int, input().split())
A = list(map(int, input().split()))
front, cycle, end, cnt = cycle_getter(K+1,1)
# print(front, cycle, end, cnt)
print((front+cycle+end)[-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dic={}
wk=1
start=0
for i in range(1,n+1):
  wk=a[wk-1]
  if wk in dic:
    start=dic[wk]
    break
  dic[wk]=i
end=len(dic)
loopcnt=end-start+1
keys=list(dic.keys())
if k<start:
  print(keys[k-1])
else:
  chk=(k-start+1)%loopcnt
  if chk==0:
    chk=loopcnt
  print(keys[(start-1)+chk-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

visited = [0] * N

current = 0
i = 1
while i <= K:
    current = A[current] - 1
    if visited[current] == 0:
        visited[current] = i
    else:
        loop = i - visited[current]
        num_loop = (K - i) // loop
        i += loop * num_loop

    i += 1

ans = current + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split())
towns = [0] + list(map(int, input().split()))
checked = [-1 for _ in range(N+1)]
checked[1] = 0
next = towns[1]
count = 1
    
while(checked[next] < 0):
  checked[next] = count
  count += 1
  next = towns[next]
loop = count - checked[next]
pos = 0
if K >= count:
  pos = checked[next] + (K-checked[next])%loop
else:
  pos = K
for i in range(1, N+1):
  if checked[i] == pos:
    print(i)
    exit()

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))
n = 1
c = 0
while n <= K:
    n *= 2
    c += 1
# print(c)
L = [[0]*(N+1) for _ in range(c)]
L[0] = A
for i in range(1, c):
    for j in range(N+1):
        L[i][j] = L[i-1][L[i-1][j]]
# print(L)

p = 1
for i in range(c):
    if (K >> i) & 1:
        p = L[i][p]
print(p)

Submission status: Accepted

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

visited = [0] * N
path = []
now_town = 1
while(True):
    visited[now_town-1] = 1
    path.append(now_town)
    now_town = As[now_town-1]
    if visited[now_town-1] == 1:
        break
index = path.index(now_town)
loop = path[index:len(path)]
loop_len = len(loop)
if index < K:
    k = K - index
    r = k % loop_len
    print(loop[r])
else:
    print(path[K])

Submission status: Accepted

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

for n in range(N-1):
  G.append(A[G[n]-1])

if len(G)<K:
  a = G.index(G[-1])
  b = len(G)-a-1
  K = (K-a)%b+a

print(G[K])

Submission status: Accepted

Solution code:
import sys
N , K = list(map(int, input().split()))
As = list(map(int, input().split()))
As = [0]+As
Came = [-1]*(N+1)

s = 1
i = 0

while True:
    if As[s] == s:
        print(s)
        sys.exit()
    elif i >=K:
        print(s)
        sys.exit()
    elif Came[s]>=0:
        break
    Came[s] = i
    i+=1
    s = As[s]
#print(Came , s)
T = i - Came[s]

L = K - Came[s]

Q = L % T
#print(T , L  , Q)
print(Came.index(Came[s]+Q))

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().split()]
a_list = [int(x) - 1 for x in input().split()]
ci = 0
while k:
    if k & 1:
        ci = a_list[ci]
    k >>= 1
    a_list = [a_list[a_list[i]] for i in range(n)]
print(ci + 1)

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().split()]
a_list = [int(x) - 1 for x in input().split()]

ci = 0
temp_dict = {0: 0}
temp_list = [0]
for i in range(1, k + 1):
    temp = a_list[ci]
    if temp in temp_dict:
        ci = temp_list[(k - i) % (i - temp_dict[temp]) + temp_dict[temp]]
        break
    temp_dict[temp] = i
    temp_list.append(temp)
    ci = temp
print(ci + 1)

Submission status: Accepted

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

dic = {}
list_town = []
set_town = set()
town = 1

for i, v in enumerate(A):
    dic[i+1] = v

for _ in range(K):
    list_town.append(town)
    set_town.add(town)
    town = dic[town]
    if town in set_town:
        stop_town = town
        break

if N <= K:
    list_first_split = list_town[:list_town.index(stop_town)]
    list_second_split = list_town[list_town.index(stop_town):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = [a-1 for a in list(map(int, input().split()))]
    visited = [0] * N
    bofore_loop_route = []
    route = []
    town = A[0]
    while True:
        if visited[town] == 0:
            visited[town] = 1
            route.append(town)
            town = A[town]
        else:
            before_loop = route.index(town)
            bofore_loop_route = route[:before_loop]
            route = route[before_loop:]
            break
    if K <= len(bofore_loop_route):
        print(bofore_loop_route[K-1] + 1)
    else:
        idx = ((K - before_loop) % len(route)) - 1
        print(route[idx] + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
b = [bi-1 for bi in list(map(int,input().split()))]
a = 0

f = [0]*n
c = 1
for i in range(k):
    if f[a]:
        k %= c-f[a]
        for i in range(k):
            a = b[a]
        print(a+1)
        break
    f[a] = c
    k -= 1
    c += 1
    a = b[a]
else:
    print(a+1)

Submission status: Accepted

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

dic = {}
list_town = []
set_town = set()
town = 1

for i, v in enumerate(A):
    dic[i+1] = v

for _ in range(K):
    list_town.append(town)
    set_town.add(town)
    town = dic[town]
    if town in set_town:
        stop_twon = town
        break

if N <= K:
    list_first_split = list_town[:list_town.index(stop_twon)]
    list_second_split = list_town[list_town.index(stop_twon):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)

Submission status: Accepted

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

dic = {}
for i, v in enumerate(A):
    dic[i+1] = v

town = 1
s = set()
l = []
for _ in range(K):
    l.append(town)
    s.add(town)
    town = dic[town]
    if town in s:
        stop_twon = town
        break
if N <= K:
    list_first_split = l[:l.index(stop_twon)]
    list_second_split = l[l.index(stop_twon):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
db = [[0]*N for _ in range(60)]
db[0] = A[:]
for i in range(1,60):
  for j in range(N):
    db[i][j] = db[i-1][db[i-1][j]]
ans = p = 0
while K>0:
  if K%2==1:
    ans = db[p][ans]
  p += 1
  K >>= 1
print(ans+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
db = [[0]*N for _ in range(100)]
db[0] = A[:]
for i in range(1,100):
  for j in range(N):
    db[i][j] = db[i-1][db[i-1][j]]
ans = p = 0
while K>0:
  if K%2==1:
    ans = db[p][ans]
  p += 1
  K >>= 1
print(ans+1)

Submission status: Accepted

Solution code:
from collections import defaultdict

N,K = map(int, input().split())
A = [int(i) for i in input().split()]
used_dict = defaultdict(int)
used_dict[0] += 1
now_town = 0
flag = False

for i in range(min(N,K)):
    now_town = A[now_town]-1
    if used_dict[now_town]:
        used_dict[now_town] += 1
        break
    used_dict[now_town] += 1
else:
    flag = True

if not flag:
    now_town2 = 0
    cnt = 0
    while 1:
        if now_town2 == now_town:
            for _ in range((K-cnt)%(i-cnt+1)):
                now_town = A[now_town]-1
            break
        now_town2 = A[now_town2]-1
        cnt += 1
print(now_town+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
prev = 0
count = 0
used = {prev: count}
for _ in range(min(k, n)):
  prev = A[prev]
  count += 1
  if prev in used:
    for _ in range((k - used[prev]) % (count - used[prev])):
      prev = A[prev]
    break
  used[prev] = count
print(prev + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
prev = 0
count = 0
used = {prev: count}
for _ in range(min(k, n)):
  prev = A[prev]
  count += 1
  if prev in used:
    break
  used[prev] = count
if count > used[prev]:
  for _ in range((k - used[prev]) % (count - used[prev])):
    prev = A[prev]
print(prev + 1)

Submission status: Accepted

Solution code:
class Telepoter:
    def __init__(self, N, K, A):
        self.N = N
        self.K = K
        self.A = A
        self.path_start = 0
        self.loop_start = -1 # 未確定、get_path_and_loopで決める
        self.path_length = -1
        self.loop_length = -1

    def find_path_and_loop(self):
        visited = [False] * self.N
        visited[0] = True
        cur = self.A[0]

        while not visited[cur]:
            visited[cur] = True
            cur = self.A[cur]

        loop_start = cur
        self.loop_start = loop_start

        # get path length
        if loop_start == 0:
            path_length = 0
        else:
            path_length = 1
            cur = self.A[0]
            while cur != loop_start:
                path_length += 1
                cur = self.A[cur]
        self.path_length = path_length

        # get loop length
        loop_length = 1
        cur = self.A[loop_start]
        while cur != loop_start:
            loop_length += 1
            cur = self.A[cur]
        self.loop_length = loop_length

    def solve(self):
        self.find_path_and_loop()

        if self.K <= self.path_length:
            cur = 0
            for i in range(K):
                cur = self.A[cur]
            print(cur+1)
            return

        self.K -= self.path_length
        self.K %= self.loop_length
        cur = self.loop_start
        for i in range(self.K):
            cur = self.A[cur]
        print(cur+1)

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

t = Telepoter(N, K, A)
t.solve()