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:
from collections import defaultdict

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

memo_first = defaultdict(int)
memo_cnt = defaultdict(int)

current = 1
cnt = 1

while K != 0:
    if memo_first[current]==0:
        memo_first[current] = cnt
    if memo_first[current] != 0 & memo_cnt[current]==0:
        memo_cnt[current] = cnt - memo_first[current]
    if memo_cnt[current] != 0:
        roop = K // memo_cnt[current]
        K = K - roop * memo_cnt[current]
    current = A[current - 1]
    K -= 1
    cnt += 1

print(current)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[1]
i=1
d={}
d[1]=1

while(True):
    j=a[i-1]
    try:
        d[j]+=1
        
    except:
        d[j]=1
        b.append(j)
    if(d[j]>1):
        y=b.index(j)+1
        
        break
    i=j
    
x=b.index(b[y-1])
z=len(b)-x
if(k<=x):
    print(b[k])
else:
    k-=x
    r=k%z
    print(b[x+r])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
aa=[0,1]+[0 for i in range(n-1)]
i=1
flag=False
l=list()
while True:
    i=a[i]
    aa[i]+=1
    if aa[i]==2 and not(flag):
        flag=True
    k-=1
    if flag:
        l.append(i)
        if aa[i]==3:
            l=l[:-1]
            break
    if k==0:
        print(i)
        exit()
print(l[k%len(l)])

Submission status: Accepted

Solution code:
n,k=map(int,input('').split(' '))
a=input('')
a=a.split(' ')
o=[]
l=[]
for p in range(n):
    a[p]=int(a[p])
    o.append(0)
    l.append('n')

p=1
h=[]
h.append(1)
j=k
aj=0
while j>0:
    p=a[p-1]
    o[p-1]+=1
    if o[p-1]>=2:
        j=j-1
        c=len(h)-l[p-1]#h.index(p)
        j=j%c

    else:
        h.append(p)
        j=j-1
    
        aj+=1
    
    l[p-1]=aj

print(p)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
X = [-1 for j in range(N)]
X[0] = 0
Y = [0]
i = 0
Num = 0
MM = 0
for k in range(1,N):
  i = A[i]-1
  if k == K:
    MM = 1
    P = i
    break
  elif X[i] != -1:
    Num = X[i]
    break
  else:
    X[i] = k
    Y.append(i)
Y = Y[Num:]
B = (K-Num)%len(Y)
if MM == 1:
  print(P+1)
else:
  print(Y[B]+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

route = [1]
index = k
hit = set([1])
for i in range(n+1):
    _next = a[route[-1]]
    if _next in hit:
        route.append(_next)
        index -= (i+1)
        break
    route.append(_next)
    hit.add(_next)

if index <= 0:
    print(route[k])
else:
    route = route[route.index(route[-1]):-1]
    print(route[index % len(route)])

Submission status: Accepted

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

passed = [False for _ in range(n)]
cur = 0
recurr_list = [cur]
passed[cur] = True
last = -1
for i in range(k):
    if passed[a[cur]]:
        last = a[cur]
        break
    else:
        recurr_list.append(a[cur])
        cur = a[cur]
        passed[cur] = True

if -1 == last:
    print(recurr_list[-1] + 1)
else:
    loop_start = recurr_list.index(last)
    loop_len = (len(recurr_list) - loop_start)
    res = (k - loop_start) % loop_len
    print(recurr_list[res + loop_start] + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,k=map(int, input().split())
A=[int(i)-1 for i in input().split()]
now=0
loop=[]
dd = defaultdict(int)
if k>=n:
    while k!=0:
        k-=1
        now = A[now]
        if dd[now]>0:
            break
        else:
            dd[now]+=1
        if k==0:
            print(now)
            exit()
        loop.append(now)
    loop = loop[loop.index(now):]
    loop.append(now)
    t = len(loop)-1
    a=(k%t)
    while a>0:
        a-=1
        now = A[now]
    print(now+1)
else:
    while k!=0:
        k-=1
        now = A[now]
    print(now+1)

Submission status: Accepted

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

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

loop = deque([0])
teleported = [False] * N

loop_start = 0
loop_end = []

while True:
    i = loop[len(loop) - 1]
    if teleported[i]:
        loop_end = [i, A[i] - 1]        
        break
    teleported[i] = True
    loop.append(A[i] - 1)

cnt = [0] * (N)

for i in range(len(loop)):
    cnt[loop[i]] += 1
    if cnt[loop[i]] == 2:
        loop_end[0] = i
        cnt[0] = loop[i]

loop_start = loop.index(cnt[0])
loop_end = loop_end[0]
loop = list(loop)
loop_2 = loop[loop_start:loop_end]

if K < loop_start:
    print(loop[K] + 1)

else:
    ans = loop_2[(K - loop_start) % len(loop_2)] + 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = (int(i) for i in input().split())
A = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

orders = []
visited = {}
cur = 1
count = 0
diff = 0
start = 0
while True:
    cur = A[cur-1]
    orders.append(cur)
    if cur not in visited:
        visited[cur] = count
    else:
        start = visited[cur]
        diff = count - start
        break

    count += 1

if K-1 < start:
    #print("he", start)
    print(orders[K-1])
else:
    #print(start, diff)
    #print(orders)
    print(orders[start+(K-1-start)%diff])

Submission status: Accepted

Solution code:
import math
from collections import defaultdict


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

    visited = [-1 for _ in range(N)]
    visited[0] = 0

    current = 0
    th = -1
    per_loop = -1
    for i in range(1, N+1):
        current = A[current] - 1

        if visited[current] >= 0:
            # print(i, current, visited[current])
            per_loop = i - visited[current]
            th = visited[current]
            break
        else:
            visited[current] = i

    current = 0
    # print(th, per_loop)

    if K < th:
        num_rep = K
    else:
        num_rep = th + (K - th) % per_loop

    for i in range(num_rep):
        current = A[current] - 1

    print(current + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
N =[0 for i in range(n)]
s = 1
cnt = 0
b = []
while True:
    if N[s-1]==1:
        rep = b.index(s)
        t = cnt-rep
        if k-rep <0:
          print(b[k])
          break
        else:
          num = (k-rep)%t
          print(b[rep+num])
          break
    else:
        b.append(s)
        N[s-1] = 1
        s = a[s-1] 
        cnt +=1

Submission status: Accepted

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

import sys

sys.setrecursionlimit(1000000000)
from collections import deque


seen = [0 for i in range(n)]

hist = deque([])  # 頂点の訪問履歴
pos = -1  # サイクルの1成分 -1はサイクル未発見


def dfs(x, p):  # pはxの親
    global pos  # global!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    seen[x] = 1
    hist.append(x)  # 訪れたらhistにappend
    if seen[A[x]-1] == 1:
        pos = A[x]-1
        return  # サイクルを発見したら、即すべてのdfsを終える
    # 残りはseen[x]=0のみ
    dfs(A[x]-1, x)
    if pos != -1: return  # 帰りがけ、サイクルが検出済みなら何もしない

    hist.pop()  # stackの末尾を消す
    # ループなく平和に終わったらpopできる
    return  # まあなくてもいいけどreturnは終了であることを強調


dfs(0, -1)

# この状態だと、サイクルに入る前に通った枝葉がhistに入ってる。
# 枝葉が終わったら、posからループの順番に頂点番号が入ってる。
cycle = []
while hist:
    qwe = hist.pop()
    cycle.append(qwe)
    if qwe == pos: break

roop = len(cycle)
sen = seen.count(1)

if k<=n:
    no = 0
    for i in range(k):
        no = A[no]-1
    print(no+1)
else:
    tmp = k-sen+roop
    tmp%=roop
    print(cycle[-tmp-1]+1)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
def minus(n):
  return n-1
  
def main():
  num_list = list(map(int, input().split()))
  A = list(map(int, input().split()))
  N=num_list[0]
  K=num_list[1]
  A_i=0
  N_list=[0]*N
  A =list(map(minus, A))
  sFlag=True
  i=0
  while(sFlag):
    i=i+1
    pre=A_i
    N_list[A_i]+=1
    if(N_list[A_i]==3):
      sumA=N_list.count(int(2))
      sumA=sumA+N_list.count(int(3))
      K=(K-i)%sumA+1
      for j in range(K):
        pre=A_i
        te=A[A_i]
        A_i=te
      sFlag=False
      break
    te=A[A_i]
    A_i=te
    if(i>=K):
      sFlag=False
      break
  print(A_i+1)
  
if __name__ == '__main__':
    main()

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

loop_lis = [0]
visited = [-1 for _ in range(N)]
visited[0] = 0
flag = 0
for i in range(K):
  if visited[A[loop_lis[-1]]] != -1:
    loop_time = i+1-visited[A[loop_lis[-1]]]
    start_loop = visited[A[loop_lis[-1]]]
    flag = 1
    break
  visited[A[loop_lis[-1]]] = i+1
  loop_lis.append(A[loop_lis[-1]])

if i == K-1 and flag == 0:
  print(loop_lis[-1]+1)
else:
  print(loop_lis[start_loop+(K-start_loop)%loop_time]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
li=list(map(int,input().split()))
H=[0]*(n)
walk=[]
x=1
l=0
e=0
while True:
    walk.append(x)
    if H[x-1]==0:
        H[x-1]=1
    else:
        dd=[i for i, j in enumerate(walk) if j == x ]
        l=1
        break
    x=li[x-1]
    e+=1
    if e==k:
        break
if l==1:
    ran=dd[1]-dd[0]
    if k>=dd[0]:
        k-=dd[0]
    kk=k%ran
    print(walk[dd[0]+kk])
else:
    print(x)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for num,i in enumerate(a):
  d[num+1] =  i
t = {}
t_ = {}
i = 1
j = 0
while(i not in t):
  t[i] = j
  t_[j] = i
  i = d[i]
  j += 1
a = 1
b = t[i]
if k < b+1:
  ans = t_[k]
else:
  k = (k-b)%(len(t.keys())-b)
  ans = t_[b+k]
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
T={}
T[1]=1
t=1
for i in range(2,K+1):
    a=A[t]
    t=a
    K-=1
    if a in T:
        l=list(T.keys())[T[a]-1:]
        print(l[K%len(l)])
        break
    else:
        T[a]=i
else:
    print(A[t])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
checked = [0]
next_num = a[0]-1
check = [0]*n
i = 0
while True:
    if i == 0:
        i += 1
    elif check[next_num] == 1:
        loop = checked[checked.index(next_num):]
        break
    checked.append(next_num)
    check[next_num] = 1
    next_num = a[next_num]-1
dif = len(checked) - len(loop)
if k <= dif:
    print(checked[k]+1)
else:
    k = k-dif
    print(loop[k%len(loop)]+1)

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

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


def func(A, town):
    return A[town]

att = 1

visited = set([1])
loopend = 0
loopstart = 0
if K > N:
    for i in range(N):
        att = func(A, att-1)
        #print(visited)
        if att in visited:
            visited = list(visited)
            loopstart = visited.index(att)
            break
        else:
            visited.add(att)
    loop = visited[loopstart:] # 周回する街
    rem = (K - loopstart) % len(loop)
    att = loop[rem]
else:
    for _ in range(K):
        att = func(A, att-1)

print(att)

Submission status: Accepted

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

current = 1
path = [1]
already = [False] * len(A)

while K > 0:
    if already[current - 1]:
        loop = path[path.index(A[current - 1]):]
        current = loop[(K - 1) % len(loop)]
        break

    path += [A[current - 1]]
    already[current - 1] = True
    current = A[current - 1]
    K -= 1

print(current)

Submission status: Accepted

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

tele = [0]
cnt = [1] + [0] * (N-1)
while True:
    nt = A[tele[-1]] -1
    if cnt[nt] == 1:
        rest = tele.index(nt) 
        roop = len(tele) - rest
        break
    tele.append(nt)
    cnt[nt] += 1

if K < len(tele):
    print(tele[K]+1)
else:
    K -= rest
    K %= roop
    print(tele[rest+K]+1)

Submission status: Accepted

Solution code:
import sys
N,K = map(int,input().split())
tele = list(map(int,input().split()))
k = 1
flag = [0]*N
goal = tele[0]
miti = [1]
while (flag[goal-1])!=1:
    k += 1
    miti.append(goal)
    flag[goal-1] = 1
    goal = tele[goal-1]
    if k == K:
        print(goal)
        sys.exit()

a = miti.index(goal)
loop = k-a
ans = miti[(K-a)%loop+a]

print(ans)

Submission status: Accepted

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

towns = [0] * N

town = 1
i = 0
while True:
    if towns[town-1] < 2:
        
        if towns[town-1] == 0:
            i += 1
            
        towns[town-1] += 1
        town = A[town-1]
    else:
        s = town
        break
    
loop = towns.count(2)
i = i - loop
k = (K - i) % loop

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

if k == 0:
    print(s)
    exit()

for _ in range(k):
    town = A[town-1]
print(town)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
loop = 1
loop_check = [0] * N
loc = A[0]
Cycle = [1]

while loop_check[loc -1] == 0:
  Cycle.append(loc)
  loop_check[loc - 1] = loop
  loc = A[loc - 1] 
  loop += 1
x = loop - loop_check[loc - 1]
if K > loop_check[loc - 1]:
  K = (K - loop_check[loc - 1]) % x + loop_check[loc - 1]
print(Cycle[K])

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
graph = [0] * N
point = 1
count = 0
flag = True
while count < K:
  graph[point-1] += 1
  count += 1
  if flag and graph[point-1] >= 3:
    stock = K - sum(graph)-1
    stock2 = sum([1 for i in graph if i >= 2])
    K = (stock % stock2) + 1
    count = 0
    flag = False
  point = A[point-1]

print(point)

Submission status: Accepted

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

L = [0] * (N+1)
now = 1
p = []
f = False

for i in range(K):
    if L[now] == 1:
        f = True
        break
    p.append(now)
    L[now] = 1
    now = A[now-1]

if f:
    for i in range(len(p)):
        if p[i] == now:
            ans = p[i + (K - i) % len(p[i:])]
            break
else:
    ans = now

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
G = dict([(i,[]) for i in range(1,N+1)])
for i in range(1,N+1):
  G[i].append(A[i])

l = deque([A[1]])
seen = [False for i in range(N+1)]
seen[1] = True
d = [0 for i in range(N+1)]
d[A[1]] = 1
if A[1] == 1:
  print(1)
  sys.exit()

for i in range(K):
  v = l.popleft()
  if seen[v] == False:
    seen[v] = True
    l.append(A[v])
    if seen[A[v]] == True: 
      a = d[A[v]]
      b = d[v] + 1 - a
    else:  
      d[A[v]] = d[v] + 1
  else:  
    start = v
    break  
  if i == K-1:
    print(v)
    sys.exit()

kaisu = (K-a)%b
p = start
for i in range(kaisu):
  p = A[p]
print(p)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
dic_A = {0:1}
direction = 0
flag = True
for i in range(K):
    direction = A_list[direction]-1
    if direction in dic_A:
        dic_A[direction] += 1
        if dic_A[direction] >= 3:
            flag = False
            break
    else:
        dic_A[direction] = 1
if flag:
    print(direction+1)
    exit()
cnt = 0
dic_ans = {}
for k, v in dic_A.items():
    if v >= 2:
        cnt += 1
        dic_ans[k] = 1
ans = K - (len(dic_A) - cnt)
ans %= cnt
for k, v in dic_ans.items():
    if ans == 0:
        true = k
        break
    ans -= 1
print(true+1)

Submission status: Accepted

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

visited_count = [0]*N

cnt = 1
next_visit = A[0] - 1
for _ in range(K):
    cnt += 1
    if not visited_count[next_visit]:
        visited_count[next_visit] = cnt
        next_visit = A[next_visit] - 1
    else:
        c2 = cnt - visited_count[next_visit]
        c1 = visited_count[next_visit] - 1
        place_count = ((K-c1) % c2) + c1 + 1
        place = visited_count.index(place_count) + 1
        print(place)
        exit(0)

place_count = K + 1
place = visited_count.index(place_count) + 1
print(place)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    [n,k] = [int(i) for i in input().split()]
    a = [int(i)-1 for i in input().split()]
    visit = []
    for i in range(n):
        visit.append(False)
    
    i = 0
    l = []
    pos = -1
    ele = -1
    while True:
        if visit[i] == True:
            ele = i
            break
        visit[i] = True
        l.append(i)
        i = a[i]
    
    pos = l.index(ele)
    period = len(l) - pos
    # print(l)
    # print(pos)
    # print(period)

    if pos == 0:
        print(l[k%period]+1)
        exit()

    ans = -1
    if k < len(l):
        ans = l[k]
    else:
        k -= pos
        pos -= 1
        p = k % period
        p+=1
        ans = l[pos+p]
    print(ans+1)

Submission status: Accepted

Solution code:
from collections import deque

n, k = map(int, input().split())
array = [int(x) - 1 for x in input().split()]
count = [-1 for x in range(n)]

now = 0
count[now] = 0
queue = deque()
queue.append(now)
dag = False
dag_start = -1
dag_end = -1
while len(queue) != 0:
    now = queue.pop()
    next_index = array[now]
    if count[next_index] != -1:
        dag = True
        dag_start = next_index
        dag_end = now
        break
    count[next_index] = count[now] + 1
    queue.append(next_index)

if count[dag_start] >= k:
    for i in range(n):
        if count[i] == k:
            print(i + 1)
            exit()
now = dag_start
d = [now]
while now != dag_end:
    d.append(array[now])
    now = array[now]
print(d[(k - count[dag_start]) % len(d)] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
list_A = list(map(int, input().split()))
list_MAP = []
set_MAP = set()
x = 1
while True:
    list_MAP.append(x)
    set_MAP.add(x)
    x = list_A[x-1]
    if x in set_MAP:
        break


q = len(list_MAP) - list_MAP.index(x)
p = k - list_MAP.index(x)

if p < 0:
    print(list_MAP[k])
else:
    list_MAP = list_MAP[list_MAP.index(x):]
    print(list_MAP[p % q])

Submission status: Accepted

Solution code:
from collections import defaultdict

n, k = map(int, input().split())
*a, = map(int, input().split())
a = [a[i] - 1 for i in range(n)]
ans = 0

if k <= n:
    i = 0
    while(k > 0):
        ans = a[i]
        i = a[i]
        k -= 1
        # print(ans + 1)
    ans += 1

else:
    # 周期の場所をチェック
    start_period = 1
    period_i = -1
    d = defaultdict(int)
    d[0] = 1
    i = 0
    count = 1
    while(1):
        # print(f'i = {i}, count = {count}')
        if a[i] in d.keys():
            period_i = count
            start_period = d[a[i]]
            break

        d[a[i]] = count + 1
        i = a[i]
        count += 1
        
    # 逆引き
    d_r = {i:k for k, i in d.items()}
    # print('d: ', d)
    # print('d_r: ', d_r)
    # print('period_i:', period_i)
    # print('start_period:', start_period)
    # print(f'{k - (start_period - 1)}')
    # print(f'{(k - (start_period - 1)) % (period_i - start_period + 1)}')
    # print('d_r[start_period]: ', d_r[start_period])
    # print(d_r[start_period + ((k - (start_period - 1)) % (period_i - start_period + 1))])
    ans = d_r[start_period + ((k - (start_period - 1)) % (period_i - start_period + 1))] + 1
    
    
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
cycle=[0]
s_cyc=set()
s_cyc.add(0)
flag=0
id=0
for i in range(N):
    a[i]-=1
while flag==0:
    if a[id] in s_cyc:
        node=cycle.index(a[id])
        break
    else:
        cycle.append(a[id])
        s_cyc.add(a[id])
        id=a[id]
if K<=node:
    print(cycle[K]+1)
else:
    K-=node
    cycle=cycle[node::]
    q=K%len(cycle)
    print(cycle[q]+1)

Submission status: Accepted

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

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

l=[1]
di={}
di[1]=1

for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
aa=0
for j in l:
    if j==x:
        break
    else:
        aa+=1

bb=len(l)-aa
if k<=aa:
    print(l[k])

else:
    cc=(k-aa)%bb
    print(l[aa+cc])

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=[0]*n
town=0
Town=0
visited[0]=0
lst=[]
if a[0]==1:
  print(1)
  sys.exit()
for i in range(n):
  town=a[town]-1
  if visited[town]!=0 or town==0:
    lst.append([town,visited[town],i+1])
    break
  else:
    visited[town]=i+1
Lst=[]
town=lst[0][0]
Lst.append(town)
if lst[0][2]-lst[0][1]-1==0:
  if k<lst[0][1]:
    print(visited.index(k)+1)
    sys.exit()
  else:
    print(lst[0][0]+1)
    sys.exit()
for i in range(lst[0][2]-lst[0][1]-1):
  town=a[town]-1
  Lst.append(town)
if k<=lst[0][1]:
  print(visited.index(k)+1)
else:
  k=k-lst[0][1]
  l=len(Lst)
  k=k%l
  print(Lst[k]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A=list(map(int,input().split()))
Acheck=[0 for i in range(N)]
nextI=1
count=0
firstCheck=True
secondCheck=True
if N<=K:
    while(secondCheck):
        Acheck[nextI-1]+=1
        if Acheck[nextI-1]==2 and firstCheck:
            #print("繰り返し始点",nextI)
            K-=count
            count=0
            firstCheck=False
        if Acheck[nextI-1]==3:
            secondCheck=False
            break
        count+=1
        nextI=A[nextI-1]
        #print(nextI,Acheck)
            
    #print(Acheck,count,nextI)
    for i in range(K%count):
        nextI=A[nextI-1]
    print(nextI)
else:
    for i in range(K):
        nextI=A[nextI-1]
    print(nextI)

Submission status: Accepted

Solution code:
def ans(n, k, list_a):
    i=0
    dic={}
    dic[1]=1
    list_memo=[1]
    while i<k:
        next = list_a[list_memo[i]-1]
        if next not in dic:
            list_memo.append(next)
            dic[next]=1
        else:
            num=list_memo.index(next)
            len_list=len(list_memo)
            i+=1
            x = len_list-num
            k=k-num
            
            #print(k)
            k%=x
            return list_memo[num+k]
            #return 50000
            
        i+=1
    return list_memo[i]
        




n, k = (int(x) for x in input().split())
list_a = list(map(int, input().split()))
print(ans(n, k, list_a))

Submission status: Accepted

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

# 閉路を求める問題。閉路が見つかれば、あとはそれを掛け算するだけ

seen_points = set([])
indexes = [-1 for _ in range(N)]
now_town = 1
index = 0
while K > 0:
    # print(f'now_town={now_town}', K, seen_points)
    # すでに見つかっているところに戻ってきたなら閉路が見つかっているはず。
    if now_town in seen_points:
        # 閉路でかかるコストはroop_count
        roop_count = index - indexes[now_town - 1]
        # なので、省略する
        if K > roop_count:
            # print(K, roop_count)
            K = K % roop_count
        seen_points = set([])
        continue
    seen_points.add(now_town)
    indexes[now_town - 1] = index
    now_town = towns[now_town - 1]
    index += 1
    K -= 1

print(now_town)

Submission status: Accepted

Solution code:
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
route = []
visited = set()
temp = 0
for i in range(N):
    route.append(temp)
    visited.add(temp)
    temp = A[temp]-1
    if temp in visited:
        before_loop = route.index(temp)
        period = len(route) - before_loop
        break
if K - before_loop < period:
    print(route[K]+1)
else:
    print(route[before_loop+(K-before_loop)%period]+1)

Submission status: Accepted

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

def findLoop():
  dp = [0 for _ in range(N)]
  next = 0;
  count = 1;
  acc = []
  while dp[next]==0:
    dp[next] = count
    acc.append(next+1)
    count += 1
    next = A[next]-1
  freq = count - dp[next]
  return(acc[:dp[next]-1], acc[len(acc)-freq:])

first, loop = findLoop()

if K<max(0, len(first)-1):
  print(first[K])
else:
  print(loop[ ( K-len(first) ) % len(loop)])

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    visited = [False] * N
    route = []
    
    cnt = 0
    v = 0
    while visited[v] == False and cnt < K:
        visited[v] = True
        route.append(v)
        v = A[v]
        cnt += 1

    if cnt < K:
        start = route.index(v)
        loop = cnt - start
        offset = (K - start) % loop
        res = route[start + offset] + 1
        print(res)
        # print(cnt)
        # print(offset)
    else:
        print(v + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import permutations


def resolve():
    n, k = map(int, input().split())
    a = list(map(lambda x :int(x)-1, input().split()))
    visited = [-1 for i in range(n)]
    route = [0 for i in range(n)]

    now = 0
    cnt = 0
    while visited[now] == -1 and cnt <= k:
        visited[now] = cnt
        route[cnt] = now
        now = a[now]
        cnt += 1
    route[cnt] = now
        

    loop = cnt - visited[now]
    tt = (k - visited[now]) % loop
    print(route[visited[now] + tt] + 1)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

b = [-1]*(n+1)
i = 0  # 回数
num = 1  # 場所
for j in range(k):
    if b[num] != -1:
        shu = i-b[num]
        ans = b[num]+(k-b[num]) % shu
        print(b.index(ans))
        exit()
    b[num] = i
    num = a[num-1]
    i += 1
print(num)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
a = na()
dp = [-1]*n
dp[0] = 0
i = 1
now = 0
loop = -1
start = -1

while True:
    now = a[now]-1
    if i == k:
        print(now+1)
        exit()
    if dp[now] == -1:
        dp[now] = i
    else:
        loop = i - dp[now]
        start = dp[now]
        break
    i+=1

print(dp.index((k-start)%loop+start)+1)

Submission status: Accepted

Solution code:
n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.insert(0,0)
start = 1
now = start
c = 0
flag = [-1]*(n+1)
while c < k and flag[now] == -1:
    #print(now)
    flag[now] = c
    c+= 1
    now = a[now]
#print(c, now)
if c == k:
    print(now)
else:
    k-=c
    cc = c-flag[now]
    nokori = k % cc
    for i in range(nokori):
        now = a[now]
    print(now)

Submission status: Accepted

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


N, K = map(int, readline().split())
A = list(map(int, readline().split()))
passed = [0] * N
P = []
c = 0
for _ in range(N):
    c = A[c] - 1
    if passed[c] == 1:
        s = c
        break
    P.append(c)
    passed[c] = 1
    
if K <= len(P):
    print(P[K-1] + 1)
else:
    idx = P.index(s)
    m = (K - idx) % (len(P) - idx)

    print(P[idx:][m-1] + 1)

Submission status: Accepted

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

aa = list(map(int, input().strip().split()))

aa = [0] + aa
bb = [False] * len(aa)

crn = 1
cnt = 1

route2 = [1]

while True:
  nxt = aa[crn]
  if bb[nxt]:
    break
  bb[nxt] = True
  crn = nxt
  route2 += [crn]
  cnt += 1
  
start = nxt
count = cnt

crn = 1
cnt = 1

route1 = [1]

while True:
  nxt = aa[crn]
  if nxt == start:
    break
  crn = nxt
  route1 += [crn]
  cnt += 1
  
route2 = route2[len(route1):]

c1 = len(route1)
c2 = len(route2)

if k < c1:
  print(route1[k])
else:
  k -= c1
  k %= c2
  print(route2[k])

Submission status: Accepted

Solution code:
import sys
n, k = map(int, input().split())
A = list(map(int, input().split()))
flags = [False] * n
steps = [0] * n
next_place = 1
step = 0
if k <= n:
    for i in range(k):
        next_place = A[next_place - 1]
    print(next_place)
    sys.exit(0)
for i in range(n):
    step += 1
    next_place = A[next_place - 1]
    if flags[next_place - 1]:
        ## 循環
        loop_start = steps[next_place - 1]
        loop_length = step - loop_start
        break
    else:
        flags[next_place - 1] = True
        steps[next_place - 1] = step
iteration = (k - loop_start) % loop_length
for i in range(iteration):
    next_place = A[next_place - 1]
print(next_place)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
x=1
l=[x]
m=[0]*n
m[x-1]=1
for i in range(n+2):
    x=a[x-1]
    if m[x-1]==0:
        m[x-1]+=1
        l.append(x)
    else:
        break
loop=l[l.index(x):]

if l==loop:
    print(loop[k%len(loop)])
else:
    f=l.index(x)
    if f>=k:
        print(l[k])
    else:
        print(loop[(k-f)%len(loop)])

Submission status: Accepted

Solution code:

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



step = [0] * (N+1)
step[0] = 1
curr = 1
cnt = 0
visited = [False] * N
first = [0] * N

while True:
      
      if visited[curr-1]:
            break
      nxt = A[curr-1]
      first[curr-1] = cnt
      visited[curr-1] = True
      step[cnt] = curr
      cnt += 1
      curr = nxt
      
#print(step, cnt, first)

if K < cnt:
  print(step[K])
else:
  step[cnt] = curr
  num_loop = cnt - first[curr-1]
  K -= first[curr-1]
  K %= num_loop
  print(step[K + first[curr-1]])
  #print(cnt, num_loop, K)

Submission status: Accepted

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

def find_min_cycle(a):
    memo = {1: 0}
    idx = 0
    cnt = 1

    while a[idx] not in memo:
        memo[a[idx]] = cnt
        cnt += 1
        idx = a[idx]-1

    return memo[a[idx]], cnt-memo[a[idx]], memo

offset, cycle_len, memo = find_min_cycle(a)
rmemo = {v: k for k, v in memo.items()}

if k <= offset:
    print(rmemo[k])
else:
    i = (k-offset)%cycle_len
    print(rmemo[offset+i])