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 = list(map(int, input().split()))
    a_list = list(map(int, input().split()))
    
    roop_count = []
    for i in range(n):
        roop_count.append(0)
    
    town = 1
    town_candidate = []
    roop_count[0] = 1
    roop_1 = 0
    roop_2 = 0
    count = 0
    for i in range(k):
        town = a_list[town-1]
        roop_count[town-1] += 1
        if roop_count[town-1] == 1:
            roop_1 += 1
        elif roop_count[town-1] == 2:
            roop_2 += 1
            town_candidate.append(town)
        elif roop_count[town-1] == 3:
            break
        count = i
    #print(roop_count)
    
    if count == k-1:
        print(town)
    else:
        town = (k-roop_1) % roop_2 -1
        print(town_candidate[town])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

curTown=1
k=0
while k<K:
    lastVisited[curTown-1]=k
    k+=1
    curTown=A[curTown-1]
    if lastVisited[curTown-1]>=0:
        p=k-lastVisited[curTown-1]
        k+=((K-k)//p)*p
        lastVisited=[-1]*N
        
print(curTown)

Submission status: Accepted

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

l = [[_, 0] for _ in range(2*n)] # [順番, 町番号]
#print(l)
cnt = [0 for _ in range(n+1)] # カウンター

tmp = 1
for i in range(1, 2*n):
    l[i][1] = tmp
    cnt[l[i][1]] += 1
    tmp = goto[tmp]
    if cnt[l[i][1]] == 2:
        x = l[i]
        break
#print(l)
#print(x)

for j in range(n):
    if l[j][1] == x[1]:
        y = l[j]
        break
#print(y)

if y[0] > k:
    print(l[k+1][1])
else:
    z = (k-y[0]+1) % (x[0]-y[0]) + y[0]
    print(l[z][1])

Submission status: Accepted

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

d = [0] * n
d[0] = 1
t = a[0]
cnt = 0
r = [1]

while d[t-1] == 0:
    cnt += 1
    d[t-1] = cnt + 1
    if k == cnt:
        print(t)
        exit()
    r.append(t)
    t = a[t-1]

rp = r[d[t-1]-1:]
b = (k-cnt) % len(rp)
print(rp[b-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(lambda x:int(x)-1, input().split()))
reached = [0 for i in range(n)]
trace = [0]
here = 0
reached[0] = 1
while reached[a[here]] != 1:
    trace.append(a[here])
    here = a[here]
    reached[here] = 1
here = a[here]
loop_start = trace.index(here)
l = len(trace)
loop = l - loop_start
if k < loop_start:
    print(trace[k]+1)
else:
    k -= loop_start
    print(trace[k % loop + loop_start]+1)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
trans = list(map(int, input().split()))
trans = [-1] + trans
dest = 1
seen = [False] * (n+1)
start = 0
output = 0
t = []
for _ in range(k):
  dest = trans[dest]
  if seen[dest]:
    for i, x in enumerate(t):
      if x == dest:
        start = i
    break
  seen[dest] = True
  t.append(dest)
if len(t) < k:
  s = t[start:]
  output = s[(k - len(t[:start]) - 1) % len(s)]
else:
  output = t[k-1]
print(output)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 20 10:11:22 2020

@author: NEC-PCuser
"""

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

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

tele_set = set()
tele_set.add(1)
junkai_town = -1 
junkai_first = -1
town = 1
for i in range(N):
    if A[town - 1] not in tele_set:
        tele_set.add(A[town - 1])
    else:
        junkai_town = A[town - 1]
        break
    town = A[town - 1] 

town = 1
start_flg = False
junkaimae_list = []
junkai_list = []
for i in range(N):
    if town == junkai_town and start_flg == False:
        junkai_first = i
        start_flg = True
    elif town == junkai_town:
        break
    if start_flg == True:
        junkai_list.append(town)
    else:
        junkaimae_list.append(town)
    town = A[town - 1]


if K < len(junkaimae_list):
    print(junkaimae_list[K])
else:
    kaisu = K - len(junkaimae_list)
    print(junkai_list[kaisu % len(junkai_list)])

Submission status: Accepted

Solution code:
import sys
import time
st = time.perf_counter()
# ------------------------------

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

cnt = [-1] * N
cnt[0] = 0
now = 0
for i in range(1, 1001001001):
    now = A[now]
    if cnt[now] == -1:
        cnt[now] = i
    else:
        circle = i - cnt[now]
        t = cnt[now]
        break
if K - t > 0:
    amari = (K - t) % circle
    for _ in range(amari):
        now = A[now]
else:
    now = 0
    for i in range(K):
        now = A[now]
print(now + 1)

# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Accepted

Solution code:
import sys
N,k=map(int,input().split())
blist=[0]+list(map(int,input().split()))

checked_list=[-1]*(N+1)
pos=1
t=0
while True:
  if t==k:
    print(pos)
    sys.exit(0)
  elif checked_list[pos]!=-1:
    break
  
  checked_list[pos]=t
  pos=blist[pos]  
  t+=1
  
#print(checked_list,pos,t)
cycle=t-checked_list[pos]
#print(cycle)
pos_in_cycle=(k-checked_list[pos])%cycle
#print(pos_in_cycle)
k2=checked_list[pos]+pos_in_cycle
#print(k2)

print(checked_list.index(k2))

Submission status: Accepted

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

    num = 1
    l = []
    s = [1]*n

    while s[num-1]:
        l.append(num)
        s[num-1] = 0
        num = a[num-1]

    if l.index(num) <= k:
        l2 = l[l.index(num):]
        kk = (k-len(set(l)-set(l2)))%len(l2)
        print(l2[kk])
    else:
        print(l[k])

main()

Submission status: Accepted

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

p = 0

if n>=k:
    for i in range(k):
        p = a[p]
    print(p+1)

else:
    lst = [-1]*n
    lst[0] = 0
    
    for i in range(1,n+1):
        p = a[p]
        if lst[p] == -1:
            lst[p] = i
        else:
            loop = i - lst[p]
            k -= lst[p]
            extra = k % loop
            break

    for i in range(extra):
        p = a[p]
    print(p+1)

Submission status: Accepted

Solution code:
#n=int(input())
n,k=map(int,input().split())
#t=int(input())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

arrived={i:False for i in range(1,n+1)}
#arrived[1]=True
city=[]
before=1
while True:
    nxt=al[before-1]
    if arrived[nxt]:
        break
    arrived[nxt]=True
    city.append(nxt)
    before=nxt
ind=city.index(nxt)
loop=city[ind:]
if k<=ind:
    ans=city[k-1]
else:
    k-=ind
    ans=loop[k%len(loop)-1]
print(ans)

Submission status: Accepted

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

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

used = [False] * N
loop = [0]  # startは0→町1
now = 0  # now+1が町
while not used[A[now]]:
    used[A[now]] = True
    loop.append(A[now])
    now = A[now]

ind = loop.index(A[now])
# new_loop = loop[(befo):]
if K < ind:
    print(loop[K]+1)
else:
    K -= ind
    K %= len(loop)-ind

    print(loop[ind+K]+1)

# print([i+1 for i in loop])
# print(new_loop[(K-befo) % (len(new_loop))]+1)

Submission status: Accepted

Solution code:
# 写経
N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
loop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        loop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(loop[(K-(len(move)-len(loop)))%len(loop)]+1)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split()) 
    al = list(map(int, input().split())) 
    city_l = [1]
    city_s = set([1])
    loop_city_l = []
    curr_city = 1
    cnt = 0
    for i in range(1,k+1):
        next_c = al[curr_city-1]
        if next_c in city_s:
            cnt = i
            first_city = city_l.index(next_c)
            loop_city_l = city_l[first_city:]
            break
        else:
            city_s.add(next_c)
            city_l.append(next_c)
        curr_city = next_c
    else:
        print(curr_city)
        return

    # print(loop_city_l)
    remained = k-cnt
    last_pos = remained%len(loop_city_l)
    print(loop_city_l[last_pos])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

gtyo = [0] *n
gtyo[0] = 1

gone = 0
t = 1

while t < n:
    gone = lis[gone] -1
    t += 1
    if gtyo[gone]:
        loop = t -gtyo[gone]
        t = n
    else:
        gtyo[gone] = t
        
if k -(gtyo[gone]-1)>= 0:
    res = (k- (gtyo[gone]-1)) % loop
else:
    res = k- (gtyo[gone]-1)
    
tmp = [i - gtyo[gone] for i in gtyo]

print(tmp.index(res)+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
dist = [-1] * n
dist[0] = 0
now = 0
while True:
    next = a[now] - 1
    if dist[next] == -1:
        dist[next] = dist[now] + 1
    else:
        hajimari = next
        loopnum = dist[now] + 1 - dist[hajimari]
        town = 0
        if k <= dist[hajimari]:
            for _ in range(k):
                town = a[town] - 1
        else:
            town = hajimari
            for _ in range((k - dist[hajimari]) % loopnum):
                town = a[town] - 1
        print(town + 1)
        exit()
    now = next

Submission status: Accepted

Solution code:
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
g = [i for i in range(n)]
for i in range(n):
    g[i] = a[i]-1
dist =[-1]*n
dist[0] = 0
q = deque([0])
hajimari = -1
loopnum = -1
while q:
    v = q.popleft()
    u = g[v]
    if dist[u] == -1:
        dist[u] = dist[v]+1
        q.append(u)
    else:
        hajimari = u
        loopnum = dist[v] + 1 - dist[u]
        break
    if hajimari != -1:
        break
if k <= dist[hajimari]:
    now = 0
    for _ in range(k):
        now = g[now]
    print(now+1)
else:
    now = hajimari
    for _ in range((k-dist[hajimari])%loopnum):
        now = g[now]
    print(now+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
li = list(map(int, input().split()))
 
check = [0] * (n)
res = []
next = 0
 
for i in range(k):
    if check[next] == 0:
        check[next] = 1
        next = li[next]-1
    elif check[next] == 1:
        check[next] += 1
        res.append(next+1)
        next = li[next]-1
    else:
        cnt = len(res)
        k -= check.count(1)
        amari = k%cnt
        print(res[amari])
        break
else:
    print(next+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
li = list(map(int, input().split()))
 
check = [0] * (n+10)
res = []
next = 0
 
for i in range(k):
    if check[next] == 0:
        check[next] = 1
        next = li[next]-1
    elif check[next] == 1:
        check[next] += 1
        res.append(next+1)
        next = li[next]-1
    else:
        cnt = len(res)
        k -= check.count(1)
        amari = k%cnt
        print(res[amari])
        break
else:
    print(next+1)

Submission status: Accepted

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

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

for i in range(k):
    num = a[num]
    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:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + A

Root = []
Visited = [0 for _ in range(N+1)]

now = 1
after = A[now]
while Visited[now] == 0:
    Root.append(now)
    Visited[now] = 1
    now = after
    after = A[now]
ind = Root.index(now)
Init = Root[:ind]
Loop = Root[ind:]

if K <= len(Init)-1:
    print(Init[K])
else:
    print(Loop[(K-len(Init))%len(Loop)])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
kari=set()
hako=set()
count=1
cnt=1
zahyo=0
ans=0
kari.add(zahyo)
if K<=10**6:
    for i in range(K):
        ans=A[ans]-1
    print(ans+1)
    exit()
for i in range(N):
    zahyo=A[zahyo]-1
    if zahyo not in kari:
        kari.add(zahyo)
        count+=1
    else:
        break

hako.add(zahyo)
for i in range(N):
    zahyo=A[zahyo]-1
    if zahyo not in hako:
        hako.add(zahyo)
        cnt+=1
    else:
        break
count=len(kari)
cnt=len(hako)
kaisu=K-count
#print(zahyo)
if kaisu>N:
    kaisu=kaisu%cnt
for i in range(kaisu):
    zahyo=A[zahyo]-1
#print(zahyo,kaisu,count,cnt)
#print(kari,hako)
print(zahyo+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
alist = list(map(lambda x:int(x) - 1,input().split()))
count = [0]*n
count[0] += 1
now = 0
order = [0]
for i in range(k):
    now = alist[now]
    count[now] += 1
    if count[now] == 2:
        start = order.index(now)
        loop = len(order[start:])
        syoki = len(order[:start])
        break
    order.append(now)
else:
    print(now+1)
    exit()
k -= syoki
k %= loop
print(order[k+syoki] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
if k <= n:
  p = 0
  for i in range(k):
    p = a[p]
  print(p + 1)
  exit()
p = 0
t = [-1]*n
t[0] = 0
for i in range(1, n):
  p = a[p]
  if t[p] != -1:
    break
  t[p] = i
d = i - t[p]
k -= i
k %= d
for i in range(k):
  p = a[p]
print(p + 1)

Submission status: Accepted

Solution code:
import sys 
from collections import deque
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,k = IL()
    a = list(IL())
    chk = [0]*n
    save = []
    current = 0
    for step in range(1,k+1):
        if chk[current]<2:
            if chk[current]==1:
                save.append(current+1)
            chk[current] += 1
            current = a[current]-1
        else:
            break
    else:
        print(current+1)
        exit()
    x = k-step+1
    x %= len(save)
    print(save[x])
    return

if __name__=='__main__':
    Main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline


def solver(N, K, A):
    i = 0
    i_list = [0]
    reached = [False for _ in range(N)]

    while True:
        next_i = A[i]
        if reached[next_i]:
            break

        reached[next_i] = True
        i_list.append(next_i)
        i = next_i

    m = i_list.index(next_i)

    if m >= K:
        return i_list[K] + 1

    le = len(i_list) - m
    K -= m
    ind = K % le

    return i_list[m + ind] + 1


def run():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = [a - 1 for a in A]

    ans = solver(N, K, A)
    print(ans)


run()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline


def solver(N, K, A):
    i = 0
    i_list = [0]
    reached = [False for _ in range(N)]

    while True:
        next_i = A[i]

        if reached[next_i]:
            break

        reached[next_i] = True

        i_list.append(next_i)
        i = next_i

    m = i_list.index(next_i)

    if m >= K:
        return i_list[K] + 1

    le = len(i_list) - m
    K -= m
    ind = K % le

    return i_list[m + ind] + 1


def run():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = [a - 1 for a in A]

    ans = solver(N, K, A)
    print(ans)


run()

Submission status: Accepted

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

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

reached = []

check = [0]*(N+1)
now = 1


for _ in range(N):
    check[now]+=1
    if check[now] == 1 :
        reached.append(now)
        now = A[now-1]

    if check[now] > 1:
        break

#print(reached)

for i in range(len(reached)):
    if reached[i]== now:
        cnt = i
        break


roop = len(reached)- cnt
init = len(reached) 

if K < init:
    print(reached[K])
else:
    print(reached[(K-init)%roop+cnt])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
l = [0 for _ in range(N)]

now = 0
l[now] = 1
count = 0
loop = [0]

while count < K:
    count += 1
    now = A[now]-1
    loop.append(now)
    if l[now] == 1:
        loop = loop[loop.index(now):-1]
        break
    else:
        l[now] = 1

if count == K:
    print(now + 1)
else:
    ans = loop[(K-count) % len(loop)]
    print(ans + 1)

Submission status: Accepted

Solution code:
# D

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

cnt = 0
temp = []

d = [0]*(2*(10**5) + 1)

now = 1
while True:
  d[now] += 1
  if d[now] > 1:
    break

  temp.append(now)
  now = A[now-1]


for t in temp[::-1]:
  cnt += 1
  if t == now:
    break

temp2 = temp[-cnt::]

if len(temp) <= K:
  kk = (K-(len(temp)-cnt))%cnt
  print(temp2[kk])
else:
  print(temp[K])

Submission status: Accepted

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

    num = 1
    l = []
    s = [1]*n

    while s[num-1]:
        l.append(num)
        s[num-1] = 0
        num = a[num-1]

    if l.index(num) <= k:
        l2 = l[l.index(num):]
        kk = (k-len(set(l)-set(l2)))%len(l2)
        print(l2[kk])
    else:
        print(l[k])

main()

Submission status: Accepted

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

isSearched = [False]*n
isSearched[0] = True
ans = []
def f():
    global k
    now = 0
    nex = A[0]
    ans.append(now)
    for i in range(k):
        now = nex
        ans.append(now)
        isSearched[now] = True
        nex = A[nex]
        if(isSearched[nex]):
            break

    if((len(ans)-1)==k):
        print(ans[-1]+1)
        return
    for i in range(len(ans)):
        if(ans[i]==nex):
            savei = i
    k -= savei
    mod = len(ans) - savei
    print(ans[savei+k%mod]+1)

f()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visit=[0]*n
visit[0]=1
now=0
c=0
for i in range(k):
  now_=now
  now=a[now]-1
  if visit[now]==0:
    visit[now]=visit[now_]+1
  else:
    c=1
    break
if c==1:
  t=(k+2-visit[now])%(visit[now_]-visit[now]+1)
  if t==0:
    print(now_+1)
  else:
    i=now
    for _ in range(t-1):
      i=a[i]-1
    print(i+1) 
else:
  u=now+1
  print(u)

Submission status: Accepted

Solution code:
import sys
n, k = [int(i) for i in sys.stdin.readline().split()]
a_s = [int(i)-1 for i in sys.stdin.readline().split()]
cnt = 0
ind = 0
ls = [ind]
last_pos = {0:0}
_set = {ind}
while cnt < k:
    ind = a_s[ind]
    if ind in _set:
        break
    _set.add(ind)
    ls.append(ind)
    cnt += 1
if cnt == k:
    print(ind+1)
else:
    start = ls.index(ind)
    end = cnt+1
    print(ls[start:][(k - cnt) % (end - start)-1]+1)

Submission status: Accepted

Solution code:
N,K,*A=map(int, open(0).read().split())
x=1
C=[None]*N
C[0]=0
c=0
while c<K:
    x=A[x-1]
    c+=1
    if C[x-1] is None:
        C[x-1]=c
    else:
        a=C[x-1]
        b=c-a
        K=(K-a)%b+a+b
        while c<K:
            x=A[x-1]
            c+=1
        break
print(x)

Submission status: Accepted

Solution code:
N, K = map(int, input().split(" "))
towns = list(map(lambda x: int(x)-1, input().split(" ")))
assert len(towns) == N

# print(towns)

# score = {0: 0}
# current = 0
# move = 0
# while 1:
#   next_town = towns[current]
#   move += 1
#   # print(f"move {current} to {next_town}")
#   if score.get(next_town) is not None:
#     # print(f"find loop!")
#     loop_move = move - score.get(next_town)
#     loop_town = next_town
#     until_loop = score.get(next_town)
#     # print(f"loop start town : ", loop_town)
#     # print(f"cost to start to loop town : ", until_loop)
#     # print(f"loop length : ", loop_move)
#     break
#   score[next_town] = move
#   current = next_town

# if K < until_loop:
#   result = 0
#   for k in range(K):
#     result = towns[result]
# else:
#   result = loop_town
#   for k in range((K - until_loop) % loop_move):
#     result = towns[result]
# print(result + 1)

L = None
visited = set([])
current = 0
while 1:
  if K == 0:
    break
  current = towns[current]
  K -= 1
  if current in visited:
    L = 0
    tcurrent = current
    while 1:
      tcurrent = towns[tcurrent]
      L += 1
      if tcurrent == current:
        break
    break
  visited.add(current)

if L is not None:
  K = K % L
  # print(K)
  for _ in range(K):
    current = towns[current]
print(current + 1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split(" "))
towns = list(map(lambda x: int(x)-1, input().split(" ")))
assert len(towns) == N

# print(towns)

score = {0: 0}
current = 0
move = 0
while 1:
  next_town = towns[current]
  move += 1
  # print(f"move {current} to {next_town}")
  if score.get(next_town) is not None:
    # print(f"find loop!")
    loop_move = move - score.get(next_town)
    loop_town = next_town
    until_loop = score.get(next_town)
    # print(f"loop start town : ", loop_town)
    # print(f"cost to start to loop town : ", until_loop)
    # print(f"loop length : ", loop_move)
    break
  score[next_town] = move
  current = next_town

if K < until_loop:
  result = 0
  for k in range(K):
    result = towns[result]
else:
  result = loop_town
  for k in range((K - until_loop) % loop_move):
    result = towns[result]
print(result + 1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
List = list(map(int, input().split()))
trace = [0]*N
pos = 1
period = 0
seppen = 0
res = 0
if K <= N:
  for i in range(K):
    if i == 0:
      pos = List[0]
    else:
      pos = List[pos-1]
  res = pos
      
else:
  for i in range(N):
    if i == 0:
      trace[i] = 1
      pos = List[0]
    else:
      if not trace[pos-1] == 0:
        period = i+1 - trace[pos-1]
        seppen = i
        break
      else:
        trace[pos-1] = i+1
        pos = List[pos-1]
  K_2 = K - seppen
  med = K_2 % period
  pos = List[trace.index(max(trace))]
  if med == 0:
    res = pos
  else:
    for i in range (med):
      pos = List[pos-1]
    res = pos
#print(trace, period,seppen)
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
 
l = [1]
for i in range(n):
    l.append(a[l[i] - 1])
 
p = l.index(l[n])
 
if k <= n:
    print(l[k])
else:
    x = (k - n + 1) % (n - p)
    if x == 0:
        print(l[n - 1])
    else:
        print(l[x + p - 1])

Submission status: Accepted

Solution code:
import sys

N, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().rsplit()))
B = [-1] * N

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

now = 0
for i in range(N):
    if B[now] == -1:
        B[now] = i
        now = A[now] - 1
    else:
        tmp = (K - B[now]) % (i - B[now])
        for i in range(tmp):
            now = A[now] - 1
        print(now + 1)
        exit()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(a)-1 for a in input().split()]
city=0
if K<=N:
    for k in range(K):
        city=A[city]
    print(city+1)
else:
    visited=[-1]*N
    for k in range(K):
        if visited[city]!=-1:
            roop_start=visited[city]
            cycle_num=k-roop_start
            break
        visited[city]=k
        city=A[city]
    K=(K-roop_start)%cycle_num+roop_start
    city=0
    for k in range(K):
        city=A[city]
    print(city+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

    now = 1
    l = []
    pre = [-1] * N
    turn = 0
    while True:
        if pre[now-1] != -1:
            break
        pre[now-1] = turn
        l.append(now)
        now = A[now-1]
        turn += 1

    if K < len(l):
        print(l[K])
    else:
        d = turn - pre[A[l[-1]-1]-1]
        f = len(l) - d
        t = (K - f) % d
        print(l[f+t])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

now = 1
B = [0] * N
cycle = -1
bC = -1

if K < N:
    for _ in range(K):
        now = A[now - 1]
    print(now)
    exit()
else:
    for i in range(N+1):
        now = A[now - 1]
        if B[now - 1] == 0:
            B[now - 1] = i
        else:
            cycle = i - B[now - 1]
            bC = B[now - 1] + 1
            break
    last = (K - bC)%cycle
    for _ in range(last):
        now = A[now - 1]
    print(now)
    exit()

Submission status: Accepted

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

cycle=[]
for i in range(0,N):
    cycle.append(-1)
    A[i]-=1

count=0
cycle[0]=count
town=0
mod=0
while True:
    count+=1
    K-=1
    town=A[town]
    if K==0:
        mod=1
        break
    if cycle[town]==-1:
        cycle[town]=count
    else:
        mod=count-cycle[town]
        break

K%=mod
while K>0:
    town=A[town]
    K-=1

print(town+1)

Submission status: Accepted

Solution code:
import math
def fact(n):
    ans = 1
    for i in range(2, n+1):
        ans*= i
    return ans
def comb(n, c):
    return fact(n)//(fact(n-c)*c)
n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt=  0
i = 1
cycle = ['1']
set = {'1'}
for c in range(n):
    i = a[i-1]
    if(i in set):
        break
    else:
        cycle.append(i)
        set.add(i)

ind = cycle.index(i)
k-= ind
rcycle = cycle[ind:]
if(k <= 0):
    print(cycle[k+ind])
else:
    now = (k+1)%len(rcycle)
    print(rcycle[now-1])

Submission status: Accepted

Solution code:
import math
def fact(n):
    ans = 1
    for i in range(2, n+1):
        ans*= i
    return ans
def comb(n, c):
    return fact(n)//(fact(n-c)*c)
'''
n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt=  0
i = 1
cycle = ['1']

for c in range(n):
    i = a[i-1]
    if(i in cycle):
        break
    else:
        cycle.append(i)

ind = cycle.index(i)
k-= ind
rcycle = cycle[ind:]
if(k <= 0):
    print(cycle[k+ind])
else:
    now = (k+1)%len(rcycle)
    print(rcycle[now-1])
'''
n,k = map(int,input().split())
a = list(map(int,input().split()))
already = ["1"]
set = {"1"}
now = 1
 
for i in range(n):
    now = str(a[int(now)-1])
    if now in set:
        break
    else:
        already.append(now)
        set.add(now)
 
 
ind = already.index(now)
k -= ind
cycle = already[ind:]
 
if k <= 0:
    print(already[k+ind])
else:
    now = (k+1) % len(cycle)
    print(cycle[now-1])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
already = ["1"]
set = {"1"}
now = 1

for i in range(n):
    now = str(a[int(now)-1])
    if now in set:
        break
    else:
        already.append(now)
        set.add(now)


ind = already.index(now)
k -= ind
cycle = already[ind:]

if k <= 0:
    print(already[k+ind])
else:
    now = (k+1) % len(cycle)
    print(cycle[now-1])

Submission status: Accepted

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

V = [-1] * n
V[0] = 0

nv = A[0]
i = 1
while True:
    if V[nv] != -1:
        first_time = V[nv]
        cycle = i - first_time
        break
    V[nv] = i
    i += 1
    nv = A[nv]

if k <= first_time:
    for idx, v in enumerate(V):
        if k == v:
            ans = idx + 1
            print(ans)
else:
    k -= first_time
    for idx, v in enumerate(V):
        if first_time + (k % cycle) == v:
            ans = idx + 1
            print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

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

    now=1
    flg = 0
    path = [1]
    pathcheck ={1}
    for i in range(min(k,n)):
        now = a[now-1]
        if now in pathcheck:
            flg = -1
            path.append(now)
            break
        path.append(now)
        pathcheck.add(now)


    if flg == 0:
        print(now)
        exit()

    x1 = path.index(now)
    x2 = len(path)-1
    x3 = (k-x1)%(x2-x1)
    print(path[x1+x3])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

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

    now=1
    flg = 0
    path = [1]
    pathcheck ={1}
    while True:
        now = a[now-1]
        flg = flg + 1
        if now in pathcheck:
            flg = -1
            path.append(now)
            break
        path.append(now)
        pathcheck.add(now)
        if flg == k:
            break


    if flg == k:
        print(now)
        exit()

    x1 = path.index(now)
    x2 = len(path)-1
    x3 = (k-x1)%(x2-x1)
    print(path[x1+x3])

if __name__ == '__main__':
    main()

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] = a[i - 1]

did = set([1])
route = [1]

now = 1
for i in range(k):
    now = d[now]
    route.append(now)
    if now in did:
        break
    did.add(now)

if k < 10 ** 6:#計算量的に間に合うので愚直に
    now = 1
    for i in range(k):
        now = d[now]

    print(now)

else:
    for i in range(len(route)):
        if route[i] == route[-1]:
            roop = route[i:-1]
            print(roop[(k - i) % len(roop)])
            exit()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

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

    now=1
    flg = 0
    path = [1]
    pathcheck ={1}
    for i in range(k):
        now = a[now-1]
        if now in pathcheck:
            flg = -1
            path.append(now)
            break
        path.append(now)
        pathcheck.add(now)


    if flg == 0:
        print(now)
        exit()

    x1 = path.index(now)
    x2 = len(path)-1
    x3 = (k-x1)%(x2-x1)
    print(path[x1+x3])

if __name__ == '__main__':
    main()