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:
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
for i in range(N):
    A[i] -= 1
P = dict()
k = 0
former = True
i = 1
while i <= K:
    if k in P.keys() and former:
        loop = i - P[k]
        K = i + (K-i) % loop
        former = False
    else:
        P[k] = i
    k = A[k]
    i += 1
else:
    print(k+1)

Submission status: Accepted

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc167/abc167_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, K = i2nn()
    A = list(map(lambda a:a-1, i2nn()))
    B = [0]
    B_rev = [None] * N
    B_rev[0] = 0
    left = 0
    for _ in range(N):
        a = A[B[-1]]
        if B_rev[a] is not None:
            left = B_rev[a]
            break
        B_rev[a] = len(B)
        B.append(a)
    #print(A)
    #print(B)
    #print(left)
    if K <= left:
        print(B[K] + 1)
        return
    p = (K - left) % (len(B) - left)
    print(B[left + p] + 1)
    return

main()

Submission status: Accepted

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

slowRunner = 0
fastRunner = 0
flag = 1
while slowRunner!=fastRunner or flag:
    flag = 0
    nextSlow = listA[slowRunner]-1
    r = listA[fastRunner]-1
    nextFast = listA[r]-1
    slowRunner = nextSlow
    fastRunner = nextFast

f = 0
slowR1 = 0
slowR2 = slowRunner
while slowR1!=slowR2:
    f+=1
    nextR1 = listA[slowR1]-1
    nextR2 = listA[slowR2]-1
    slowR1 = nextR1
    slowR2 = nextR2

nodeL = []
start = slowR1
s = slowR1
flag = 1
while s!=start or flag:
    flag = 0
    nodeL.append(s+1)
    next = listA[s]-1
    s = next

if k > f:
    amari = (k-f)%len(nodeL)
    print(nodeL[amari])
else:
    i = k
    r = 0
    while i > 0:
        next = listA[r]-1
        r = next
        i-=1
    print(r+1)

Submission status: Accepted

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

lm = [1] * (n + 1)
visited = [False] * (n + 1)
firstVst = [-1] * (n + 1)

cycle = n
start = k

for i in range(n):
    lm[i + 1] = la[lm[i] - 1]
    if not visited[lm[i] - 1]:
        visited[lm[i] - 1] = True
        firstVst[lm[i] - 1] = i
    else:
        cycle = i - firstVst[lm[i] - 1]
        start = min(start, firstVst[lm[i] - 1])

if cycle == n:
    start = 0
# print(cycle)
# print(start)
# print(firstVst)
# print(lm)

m = (k - start) % cycle
# print(m)

print(lm[start + m])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]
w=set([0])
x=0
for i in range(n):
    if a[x]-1 not in w:
        d.append(a[x]-1)
        w.add(a[x]-1)
        x=a[x]-1
    else:
        f=a[x]-1
        break

#print(d)
if k<len(d):
    print(d[k]+1)
else:
    x=k-len(d)
    y=d.index(f)
    z=len(d)-y
    #print(d,f,x,y,z)
    #exit()
    print(d[y+x%z]+1)

Submission status: Accepted

Solution code:
N,S=list(map(int, input().split())) 
tele=list(map(int, input().split())) 
for i in range(N):
    tele[i]-=1
loop=[0]*N
order=[]
now=0
cnt=0
while loop[now]!=1:
    loop[now]=1
    order.append(now)
    cnt+=1
    now=tele[now]

looptime=0
i=0
for i in range(cnt):
    if order[i]==now:
        looptime=cnt-i
        break
mod=(S-i)%looptime
if S-i<0:
    print(order[S]+1)
else:
    if (mod+i==len(order)):
        print(order[i]+1)
    else:
        print(order[mod+i]+1)

Submission status: Accepted

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

if K <= 200000:
  i = 1
  for _ in range(K):
    i = A[i-1]
  print(i)
  exit()

visited = {1}
order = [1]

i = 1
for count in range(1, 200001):
  i = A[i-1]
  if i in visited:
    break
  else:
    visited.add(i)
  order.append(i)

idx = order.index(i)
order2 = order[idx:]
# print(order2)
mod = (K+1-idx) % len(order2)

print(order2[mod-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
b=list(map(int,input().split()))
v=[None]*n
w=[0]*n
i,c=0,b[0]
while v[c-1] is None:
    w[i]=c
    v[c-1] = i
    i+=1
    c=b[c-1]

head = v[c-1]
loop = i-v[c-1]
if k-1 < head:
    print(w[k-1])
else:
    print(w[head + ((k-1-head)%loop)])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
l1 = list(map(int,input().split()))
l = list(i-1 for i in l1)
bit = list(0 for i in range(n))
bit[0] =1
mi = [0]
m = l[0]
er = 0
while er ==0:
  if bit[m]==1:
    a = mi.index(m)
    r = mi[a:]
    er  =1
  else:
    bit[m] = 1
    mi.append(m)
    m = l[m]
 # print(bit)
be = mi[:a]+r
#print(be,r)
if k< len(be):
  print(be[k]+1)
else:
  w = k-len(be)+1
  u = (w%len(r))-1
  print(r[u]+1)

Submission status: Accepted

Solution code:
def D():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    next = a[0]
    path = [1]
    visited = [True] + [False]*(n-1)
    while not visited[next-1]:
        k -= 1
        if k==0:
            print(next)    
            break
        path.append(next)
        visited[next-1] = True 
        next = a[next-1]
    if k!=0:
        cyclic = path[path.index(next):]
        print(cyclic[k%(len(cyclic))-1])

D()

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
stack = deque([])
passed = set()
town = 0
while town not in passed:
    passed.add(town)
    stack.append(town)
    town = A[town] - 1

if len(stack) > K:
    print(stack[K] + 1)
    import sys
    sys.exit()

tail = 0
while stack[0] != town:
    _ = stack.popleft()
    tail += 1

K -= tail
K += 1
tmp = K % len(stack)
if tmp == 0:
    tmp = len(stack)
print(stack[tmp - 1] + 1)

Submission status: Accepted

Solution code:
import sys
N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

x = A[0]
visited = [0] * N
visited[0] = 1
visited_num = [1]
for i in range(N):
    if visited[x - 1] == 1:
        b = i + 1
        break
    visited[x - 1] = 1
    visited_num.append(x)
    x = A[x - 1]
    
for j, p in enumerate(visited_num):
    if p == x:
        a = j
        
if K < a:
    ans = visited_num[K]
else:
    n = (K - a) % (b - a)
    ans = visited_num[a + n]
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=numpy.zeros(n,dtype=int)

city=1
count=0
while b[city-1]==0:
    count+=1
    b[city-1]=1
    
    city=a[city-1]

#arrive at city in count, len(cl)=count
if k<count:
    cc=1
    for i in range(k):
        cc=a[cc-1]
    print(cc)
    sys.exit()

c=1
cnt=0
while c!=city:
    cnt+=1
    c=a[c-1]

loop=count-cnt

d=(k-count)%loop

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

print(city)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

log = []
check = [False]*N

def func(x, iter):
    x = A[x-1]

    if iter+1 == K:
        return x
    if check[x-1]:
        ix = log.index(x)
        loop = log[ix:]
        tmp = (K-iter-1)%len(loop)
        return loop[tmp]
    else:
        log.append(x)
        check[x-1] = True
        iter += 1
        return func(x, iter)

print(func(1, 0))

Submission status: Accepted

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

visited=[0]*N#訪問フラグ
ima_pos=0#現在地
mirai_pos=0#移動先

count_first=0#一巡目のループ
first_DP=[]
while(visited[ima_pos]==0):
  visited[ima_pos]=1#訪れたら更新
  mirai_pos=A[ima_pos]-1
  ima_pos=mirai_pos
  first_DP.append(ima_pos)#何番目のインデックスに移動するか
  count_first+=1#何回移動したか

second_start=ima_pos#2巡目ループのスタート地点
count_second=0#2巡目以降のループ
second_DP=[]

while(True):#スタート地点に戻ってきたら抜ける
  visited[ima_pos]=2#訪れたら更新
  mirai_pos=A[ima_pos]-1
  ima_pos=mirai_pos
  second_DP.append(ima_pos)
  count_second+=1#何回移動したか
  if ima_pos==second_start:
    break

#各DPには何番目(0から)スタートの町に行くか　が書かれている
if K<=count_first:
  print(first_DP[K-1]+1)
elif K>count_first:
  cc=K-count_first#残り何回移動するか
  if cc%count_second==0:
    print(second_DP[-1]+1)
  else:
    print(second_DP[cc%count_second-1]+1)

Submission status: Accepted

Solution code:
s = input().split()

n = int(s[0])
k = int(s[1])

a = input().split()

siyouzumi = {1}
y = [1]
t = 1

for i in range(1,k+1):

    t = int(a[t-1])
    if t in siyouzumi:
        haba = i - y.index(t)
        kaisu = int((k - i) / haba)

        l = k - (i + (haba * kaisu))

        for j in range(l):
            t = int(a[t-1])
        break

    siyouzumi.add(t)
    y.append(t)


print(t)

Submission status: Accepted

Solution code:
import sys
a,b=map(int,input().split())
b=b+1
l=[0]*(a)
List=list(map(int,input().split()))
i=0
j=1
while l[i]==0 and j<b:
  l[i]+=j
  j+=1
  i=List[i]-1
if j==b:
  print(i+1)
  sys.exit()
roop=j-l[i]
c=(b-j)%roop
for y in range(len(l)):
  if l[y]==c+l[i]:
    print(y+1)
    sys.exit()

Submission status: Accepted

Solution code:
def main():
    n, k = [int(x) for x in input().split()]
    teleporter = [int(x) - 1 for x in input().split()]
    route = []
    route_append = route.append
    seen = [False] * n
    traveled, now_i = 0, 0

    while traveled < n + 100:
        if seen[now_i]:
            # テレポートがループしたら，ルート調査は終了する。
            break
        route_append(now_i)
        seen[now_i] = True
        now_i = teleporter[now_i]
        traveled += 1

    # 調査終了後，now_1 はループ部分の頭。ループ前にイントロがある。
    # ループ頭は何番目に尋ねるか？
    # intro_length = [i for i, x in enumerate(route) if x == now_i][-1]
    intro_length = route.index(now_i)
    loop_length = len(route) - intro_length
    if k >= intro_length:
        arriving_i = intro_length + (k - intro_length) % loop_length
    else:
        # k が イントロ内に収まっている場合。
        arriving_i = k
    return route[arriving_i] + 1


if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

curr = 0
cnt = 0
k += 1
while k > 1:
  if b[curr] != -1:
    loop = cnt - b[curr]
    break
  b[curr] = cnt
  cnt += 1
  k -= 1
  curr = a[curr] - 1

if k != 1:
  mod = k % loop
  for i in range((mod-1) % loop):
    curr = a[curr] - 1

print(curr + 1)

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input = sys.stdin.readline
    n,k=L()
    a=L()
    visited=[0]*(n+1)
    tmp=0
    now=0
    visited[0]=1
    loopat=-1
    for i in range(k):
        #print(visited,end="")
        tmp=i+2
        now=a[now]-1
        #print(now)
        #print(tmp,now+1)
        if visited[now]==0:
            visited[now]=i+2
        else:
            loopat=now
            break
    #print(visited)
    #print(loopat,visited[loopat],tmp)
    #print(tmp,now)
    if loopat==-1:
        print(now+1)
        exit()
    elif tmp-visited[loopat]==0:
        tmp2=k
        dist=1
        now=0
    else:
        tmp2=(k-(visited[loopat]-1))%(tmp-visited[loopat])
        dist=loopat+1
    #print(tmp2)
    
    #print(now,dist)
    #print(now+1,end=" ")
    for i in range(tmp2):
        now=a[now]-1
        dist=now+1
        #print(now,dist)
    #print()
    print(dist)
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1


def II(): return int(input())


def MI(): return map(int, input().split())


def MI1(): return map(int1, input().split())


def LI(): return list(map(int, input().split()))


def LI1(): return list(map(int1, input().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))


INF = float('inf')


def solve():
    n, k = MI()
    A = LI1()
    # print(A)
    memo = {0: 0}
    current = 0
    keiro = []
    for i in range(n):
        keiro.append(current)
        next = A[current]
        # print(i, current, next)
        if (i + 1) == k:
            print(next+1)
            return

        if memo.get(next, -1) == -1:
            memo[next] = i + 1
            current = next
        else:
            pre = current
            current = next
            keiro.append(current)
            # print(pre, current)
            left = k - i - 1
            # print('aaa', memo[pre], memo[current])
            loopsize = memo[pre] - memo[current] + 1
            # print('a', left, loopsize)
            r = left % loopsize
            # print(memo)
            # print(keiro)
            # print(keiro[memo[current] + r])
            ans = keiro[memo[current] + r] + 1
            print(ans)
            return


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    a, i = [1], 0
    for _ in [0] * N:
        a.append(A[i])
        i = A[i] - 1

    if K <= N:
        print(a[K])
        return

    n = defaultdict(list)
    for i, v in enumerate(a):
        if n[v]:
            n[v].append(i)
            break
        n[v].append(i)
    l, r = n[v][0], n[v][1]
    loop = a[l:r]
    K -= l
    n = K % (r - l)
    print(loop[n])


main()

Submission status: Accepted

Solution code:
import itertools

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

# まずループを見つけてみる

loopstart = -1
loopend = -1
path = []
nextcity = 0
FLAGS = [False for _ in range(N)]
for i in range(N):
    currentcity = nextcity
    path.append(nextcity)
    FLAGS[nextcity] = True
    nextcity = A[nextcity]-1
    if FLAGS[nextcity]:
        loopstart = nextcity
        loopend = currentcity
        path.append(nextcity)
        break
#print(path)

# ループまでの距離
toloop = path.index(loopstart)

# ループ内の距離
looplength = path.index(loopend) - toloop + 1

#print(toloop)
#print(looplength)
if K < toloop + looplength + 1:
    print(path[K] + 1)
else:
    fromloopstart = (K - toloop) % looplength
    print(path[toloop + fromloopstart] + 1)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cycle = 0
    flag = True
    visited = [0] * N
    visited[0] = 1
    visited_num = [0] * N
    before_city = 0
    visited_city = 0
    periodic = 0
    while flag:
        next_city = A[before_city] - 1
        cycle += 1
        if cycle >= K:
            flag = False
        if visited[next_city] == 1:
            visited_city = next_city
            periodic = cycle - visited_num[next_city]
            flag = False
        else:
            visited[next_city] = 1
            visited_num[next_city] = cycle
            before_city = next_city
    #print(periodic)
    #print(visited_city)
    if cycle < K:
        K_new = (K - cycle) % periodic
        before_city = visited_city
        for i in range(K_new):
            next_city = A[before_city] - 1
            before_city = next_city
        print(next_city+1)
    else:
        print(next_city+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

if a[0] == 1:
  print(1)
  exit()
  
log = np.full(n, -1)
log[0] = 0
step = 0
now = 0
flag = 0
while step < k:
  now = a[now] - 1
  step += 1
  if log[now] != -1:
    flag = 1
    break
  else:
    log[now] = step

if flag == 0:
  print(now+1)
  exit()

loop = step - log[now]
remain = k - step
if remain > loop:
  remain = remain % loop

for i in range(remain):
  now = a[now] - 1
print(now+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[i-1 for i in A]
c=A[A[0]]
 
s=set()
s.add(0)
s.add(A[0])
I=[]#訪れた島を記憶
I.append(0)
I.append(A[0])

while True:
  if c in s:
    break
  s.add(c)
  I.append(c)
  c=A[c]

a=I.index(c)
if K>=a:
  K-=a
else:
  ans=0
  for i in range(K):
    ans=A[ans]
  print(ans+1)
  exit()

ans=0
for i in range(a):
  ans=A[ans]
#ansが今いる島
mod=len(s)-a
K%=mod

if K==0:
  print(ans+1)
  exit()
#ans=A[0]
#for i in range(a):
#  ans=A[ans]

for i in range(K):
  ans=A[ans]
print(ans+1)

Submission status: Accepted

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

X = [-1] * N
i = 0
t = 0
while X[i] < 0:
    X[i] = t
    i = A[i]
    t += 1

X[i] + (K - X[i]) % (t - X[i])

if K <= X[i]:
    print(X.index(K) + 1)
else:
    print(X.index(X[i] + (K - X[i]) % (t - X[i]) ) + 1)

Submission status: Accepted

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


#一回あたりのループを計算（何回で戻ってくるか）
#ループの箇所を見つける
trace = [0]*N
loop_start = 0
loop_before = 0
cnt = 0
all_cnt = 0

if K > N:
    loop = 0
    now = 0
    while(1):
        # print(trace)
        trace[now] += 1
        if trace[now] == 3:
            break
        if trace[now] == 2:
            cnt += 1
            loop += 1 
            if cnt == 1: 
                loop_start = now
                loop_before = all_cnt
        now = A[now]-1
        all_cnt += 1

    loop_before = loop_before - loop 

    # print(loop)
    # print(loop_start)
    # print(loop_before)
    # print(loop)
    min_K = (K-1-loop_before) % loop
    # print(min_K)
    # print(loop_before)
    now = 0
    for i in range(loop_before):
        now = A[now]-1
    for i in range(min_K):
        now = A[now]-1
    print(A[now])

if K <= N:
    now = 0
    for i in range(K-1):
        now = A[now]-1
    print(A[now])


# print(K % 3)

# print(now+1)

Submission status: Accepted

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

    p_bool = [False] * n
    ne_p = 1
    p_bool[ne_p-1] = True
    step = 0
    for i in range(n):
        ne_p = a[ne_p-1]
        step += 1
        if p_bool[ne_p-1]:
            break
        else:
            p_bool[ne_p-1] = True
        if step == k:
            print(ne_p)
            sys.exit()
    
    p_list = []
    sta = ne_p
    for i in range(n):
        ne_p = a[ne_p-1]
        step += 1
        p_list.append(ne_p)
        if ne_p == sta:
            break
        if step == k:
            print(ne_p)
            sys.exit()

    len_l = len(p_list)
    left = k-step
    left -= (left//len_l) * len_l
    print(p_list[left-1])
    # p_list = [1]
    # ne_p = a[0]
    # p_bool = [False] * n
    # p_bool[0] = True
    # check = False
    # step = 0
    # for _ in range(n):
    #     p_bool[ne_p-1] = True
    #     p_list.append(ne_p)
    #     step = 0
    #     if step == k:
    #         #print(ne_p)
    #         sys.exit()
    #     ne_p = a[ne_p-1]
    #     # if ne_p in p_list:
    #     #     ind = p_list.index(ne_p)
    #     #     break
    #     if p_bool[ne_p-1]:
    #         check = True
    #         break
        
    # #print(p_list)
    # #print(p_bool)
    # if check:
    #     ind = p_list.index(ne_p)
    # else:
    #     ind = 0
    # k = k - ind
    # #print(ind)
    # #print(k)
    # #print(p_list)
    # #print(k%(len(p_list)-ind))
    # print(p_list[ind + k%(len(p_list)-ind)])

solve()

Submission status: Accepted

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

a = list(map(int, input().split()))
done = [0]*n
stay = 1

for i in range(1, k+1):
    if done[stay-1] != 0:
        break
    done[stay-1] = i
    stay = a[stay-1]

nokori = k + 1 - i
if nokori != 1:
    loop = i - done[stay-1]
    for i in range(nokori%loop):
        stay = a[stay-1]

print(stay)

Submission status: Accepted

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

reached = [0] * N

next = A[0]
cnt = 1
while not reached[next]:
    reached[next] = cnt
    next = A[next]
    cnt += 1

cnt2 = 1
start = next
#print("start:"+ str(start))
next = A[start]
while  start != next:
    cnt2 += 1
    next = A[next]

if K < cnt:
    #print("K<cnt")
    for i in range(N):
        if reached[i] == K:
            print(i+1)
elif K == cnt:
    #print("K==cnt")
    print(start+1)
elif K > cnt:
    #print("K > cnt")
    #print("K:"+str(K))
    #print("cnt:"+str(cnt))
    #print("cnt2:"+str(cnt2))
    tmp = K - cnt
    r = tmp % cnt2
    next = A[start]
    for i in range(r-1):
        next = A[next]
    if r == 0:
        print(start+1)
    else:
        print(next+1)

Submission status: Accepted

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

roopStart = -1
roopCount = 0
firstMove = 0
now = 0
trace = [0] * n

for i in range(2 * n):
    if trace[now] == 1 and roopStart == -1:
        roopStart = now

    if trace[now] == 2:
        break

    if roopStart != -1:
        roopCount += 1
    else:
        firstMove += 1

    trace[now] += 1
    now = a[now] - 1

firstMove -= roopCount

now = 0
if k < firstMove:
    for i in range(k):
        now = a[now] - 1
    print(now + 1)
else:
    for i in range(firstMove):
        now = a[now] - 1

    k -= firstMove
    k %= roopCount
    for i in range(k):
        now = a[now] - 1
    print(now + 1)

Submission status: Accepted

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

visited = set()
visited_list = []
index = 0
visited.add(index)
visited_list.append(0)
count = 0
flag = False
for i in range(K):
    index = As[index] - 1
    count += 1
    if index in visited:
        flag = True
        break
    visited.add(index)
    visited_list.append(index)

temp_index = visited_list.index(index)
K -= count
count = count - temp_index

if flag:
    K %= count
    for i in range(K):
        index = As[index] - 1

print(index+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 = list(map(int, input().split()))
    A = [x-1 for x in list(map(int, input().split()))]

    len_cycle = 0
    start = 0
    already_visit = set([0])

    loop_node = -1
    if K > N:
        while True:
            start = A[start]
            len_cycle += 1
            if start in already_visit:
                loop_node = start
                break
            else:
                already_visit.add(start)

        dist_loop_node = 0
        if loop_node != 0:
            start = 0
            while True:
                start = A[start]
                dist_loop_node += 1
                if start == loop_node:
                    break
            len_cycle -= dist_loop_node

        len_move = (K - dist_loop_node) % len_cycle
        start = loop_node
        for _ in range(len_move):
            start = A[start]
        print(start+1)
    else:
        start = 0
        for _ in range(K):
            start = A[start]
        print(start+1)
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
towns = [int(s) for s in input().split()]
pos = []
pos_set = set()
cur = towns[0]
i = 0
end = False
while not cur in pos_set:
    i += 1
    if k == i:
        print(cur)
        end = True
        break
    pos.append(cur)
    pos_set.add(cur)
    cur = towns[cur-1]

if not end:
    j = pos.index(cur)
    print(pos[(k-j-1)%(len(pos)-j) + j])

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
K -= 1
A = list(map(lambda x: int(x) - 1, input().split()))
seen = [None]*N
seen_set = set()
now = 0
for i in range(N):
    seen[i] = now
    seen_set.add(now)
    to = A[now]
    now = to
    if now in seen_set:
        seen[i+1] = now
        loop_s = seen.index(now)
        loop_end = i + 1
        size = loop_end - loop_s
        break
if K <= loop_s:
    print(seen[K+1] + 1)
else:
    K -= loop_s
    print(seen[loop_s + 1 + K % size] + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[0]+[-1]*(n-1)
p=1
c=0
s=-1
e=-1
for i in range(n):
    p=A[p-1]
    c+=1
    if C[p-1]==-1:
        C[p-1]=c
    else:
        s=C[p-1]
        e=c
        break
P=1
if s!=-1 and e!=-1:
    if k<=s:
        while k>0:
            P=A[P-1]
            k-=1
        print(P)
    else:
        l=(k-s)%(e-s)
        k=s+l+1
        while k>1:
            P=A[P-1]
            k-=1
        print(P)
else:
    if k<=n:
        while k>0:
            P=A[P-1]
            k-=1
        print(P)
    else:
        while n>0:
            P=A[P-1]

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
passlist = [0]*N
point = 1
depth = 0
waylist = []
while passlist[point-1] == 0:
    waylist.append(point)
    passlist[point-1] = depth
    point = A[point-1]
    depth+=1
roop = waylist[waylist.index(point):len(waylist)]
firstreach = passlist[roop[0]-1]
if K < firstreach:
  print(passlist.index(K)+1)
else:
  print(roop[(K-firstreach)%len(roop)])

Submission status: Accepted

Solution code:
import numpy as np
import math

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


visited = {}
next=1
start=-1
loop_num=0
while(K>0):
	#print(next,start)
	if next==start:
		break
	if not next in visited.keys():
		visited[next] = 1
	elif start==-1:
		start=next
		loop_num=0
	next = A[next-1]
	K-=1
	loop_num+=1


if K==0:
	print(next)
else:
	K%=loop_num
	next=start
	for i in range(K):
		next = A[next-1]
	print(next)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    lenA = len(A)

    tmp = []
    path = []
    setpath = set([])
    cnt = 0
    i = 1
    for _ in range(1, N+10):
        setpath.add(i)
        path.append(i)
        if len(setpath) != len(path):
            path.pop()
            itmp = path.index(i)
            break
        i = A[i-1]

    lenpath = len(path)
    if K >= lenpath:
        jtmp = (K-itmp)%(lenpath-itmp)
        ans = path[itmp+jtmp]
    else:
        ans = path[K]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = [0 for _ in range(n)]
f[0] = 1

v = [1]
s = 0
idx = 0
loop = 0
last = 1
for i in range(k):
    vi = a[last - 1]
    if not f[vi - 1]:
        f[vi - 1] = 1
        last = vi
        s += 1
        v.append(vi)
    else:
        s += 1
        idx = v.index(vi)
        loop = s - idx
        break
else:
    print(vi)
    exit()
remain = k - s
print(v[idx:][remain % loop])

Submission status: Accepted

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

A_list = list(map(int, input().split()))
A_list = [A - 1 for A in A_list]

path = [0]
town = 0
k = K
j = 0

while k > 0:
  town = A_list[town]
   
  if k % 10000 == 0:
    if town in path:
      #print("town is {}".format(town))
      #print("path is {}".format(path))
      first_visit = path.index(town)
      loop_size = j - first_visit + 1
      #print("loop_size is {}".format(loop_size))
      #print("k is {}".format(k))
      k = (k-1) % loop_size 
      #print("k is now {}".format(k))
      town = path[first_visit + k]
      break
    
  path.append(town)
    
  k = k - 1
  j = j + 1

print(town+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = 1
c = [0] * n
c[0] = 1
m = 0
while c[b-1] < 2 and k > 0:
	b = a[b-1]
	c[b-1] += 1
	k -= 1
while c[b-1] < 3 and k > 0:
	b = a[b-1]
	c[b-1] += 1
	m += 1
if k == 0:
	print(b)
else:
	o = k % m
	for i in range(o):
		b = a[b-1]
	print(b)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, K, A):
    n = 1
    k = 0
    d = {n: k}
    while True:
        k += 1
        n = A[n - 1]
        if k == K or n == A[n - 1]:
            return n
        if not n in d:
            d[n] = k
        else:
            x = (K - d[n]) % (k - d[n]) + 1
            for i in d:
                if d[i] == d[n] - 1 + x:
                    return i
            return -1

    

(N, K) = tuple([int(s) for s in input().split()])
A = [int(s) for s in input().split()]
print(calc(N, K, A))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def main():
    N, K = [int(i) for i in input().split()]
    teleporters = [int(i) for i in input().split()]

    # step1: find loop
    visited = set()
    visited.add(1)
    pos = 1
    loop = [1]
    while True:
        next = teleporters[pos-1]
        if next not in visited:
            pos = next
            visited.add(next)
            loop.append(next)
        else:
            loop_start = loop.index(next)
            break

    init = loop[:loop_start]
    loop = loop[loop_start:]
    if K < len(init):
        return init[K]
    else:
        K = K - len(init)
        return loop[K % len(loop)]


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    visited = [False for i in range(N)]

    ind = 0
    cnt_toloop = 0
    for i in range(N):
        if visited[ind] == False:
            visited[ind] = True
            ind = A[ind] - 1
            cnt_toloop += 1
        else:
            break

    start = ind
    ind = start
    cnt = 0
    for i in range(N):
        if A[ind] - 1 == start:
            cnt += 1
            break
        else:
            ind = A[ind] - 1
            cnt += 1

    step = 0
    ind = 0
    
    if K >= cnt_toloop:
        K -= cnt_toloop
        K = K % cnt

        step = cnt_toloop + K

        for i in range(step):
                ind = A[ind] - 1
        print(ind + 1)
   
    else:
        step = K
        for i in range(step):
            ind = A[ind] - 1
        print(ind + 1)
    
if __name__ == "__main__":
    main()