Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
point=1
m,l=0,0
if K>N:
    for i in range(N):
        if B[point-1]==0:
            B[point-1]=i+1
            point=A[point-1]
        else:
            m=i+1-B[point-1]
            l=B[point-1]
            break
    if m!=0:
        m=(K-l)%m
    else:
        m=N
else:
    m=K
ans=1
for i in range(l+m):
    ans=A[ans-1]
 
print(ans)

Submission status: Accepted

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

dist = [0 for i in [0]*(n+1)]
idx = 1
d = 1
while not dist[idx] and d<k+1:
    dist[idx] = d
    idx = a[idx-1]
    d += 1
    #print(dist)
if d==k+1:
    print(idx)
else:
    rem = dist[idx] - 1
    cyc = d - dist[idx]
    k -= rem
    k %= cyc
    for i in range(k):
        idx = a[idx-1]
    print(idx)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
button = list(map(int,input().split()))
visit = [-1]*n
hisitory = [-1]
push = 0
f = 0

for i in range(k):
    visit[push] = i+1
    hisitory.append(push)
    push = button[push] -1
    if(visit[push] != -1):  
        f = 1
        start = visit[push]
        last=push
        end = i+1
        break
if(f == 0):
    print(button[hisitory[-1]])
else:
    geta = start -1
    loopk = k - geta
    loop = end -start + 1
    modk = loopk%loop
    if(modk == 0):
        modk = loop
    print(button[hisitory[geta + modk]])
    # print(hisitory)
    # print(geta,modk,loop)

Submission status: Accepted

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

a = [i-1 for i in a]

d = [1]*n
p = 0
b = []
while d[p]:
    b.append(p)
    d[p] = 0
    p = a[p]
avant = b.index(p)
loop_count = len(b) - avant
c = b[avant:]

if k <= avant:
    print(b[k]+1)
else:
    k -= avant
    k %= loop_count
    print(c[k]+1)

Submission status: Accepted

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

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

now = 0
flag = True
for i in range(10 ** 5 * 5):
    if first_visit[now] == 0:
        first_visit[now] = i

    visited[A[now] - 1] += 1
    now = A[now] - 1

    if i == K - 1:
        print(now + 1)
        flag = False
        break

if flag:
    num = 0
    for i in range(N):
        if visited[i] > 2:
            num += 1

    for i in range(N):
        if visited[i] >= 2:
            if K % num == first_visit[i] % num:
                print(i + 1)
                break

Submission status: Accepted

Solution code:
def main():
    n,k=map(int,input().split())
    a=[int(i)-1 for i in input().split()]
    visit=[False]*n
    visit[0]=True
    loop, loopstart, loopout, cur=0, -1, False, 0
    i = 0
    while i < k:
        #print("{}->{}".format(cur+1, a[cur]+1))
        cur=a[cur]
        if not loopout and visit[cur]:
            #print("OnLoop", k)
            if loopstart == cur:
                k=(k-sum(visit))%loop
                loopout=True
                #print("OutLoop", k)
                i = 0
                continue
            elif loopstart == -1:
                #print("loop start with", cur+1)
                loopstart = cur
            loop+=1
        else:
            visit[cur]=True
        i += 1
    print(cur+1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def solve(A, K):
    a = deque() # 繰り返し部分
    seen = [False for _ in range(len(A))] # 一度見たかどうか
    cur = 0
    while True:
        # 一度通った頂点を見つけたときの処理
        if seen[cur]:
            while a[0] != cur:
                # 最初の余計な数手分を除去する
                K -= 1
                a.popleft()

                # K が限界になったらリターン
                if K == 0:
                    return a[0] + 1
            break

        # 最初は愚直にシミュレーションしつつ、履歴をメモしていく
        a.append(cur)
        seen[cur] = True
        cur = A[cur]        
    return a[K % len(a)] + 1

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

Submission status: Accepted

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

for i in range(N):
  v[n] = i
  n = A[n]
  if v[n] != -1:
    s = n
    t = i
    l = t - v[s] + 1
    break

if t >= K:
  print(v.index(K))
else:
  K = (K - v[s]) % l
  print(v.index(K + v[s]))

Submission status: Accepted

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

v = [-1] * (N + 1)
n = 1
f = 0

for i in range(N):
    v[n] = i
    n = A[n]
    if v[n] != -1:
        f = 1
        s = n #ループのスタート
        t = i
        l = t - v[s] + 1
        break

if t >= K:
    print(v.index(K))
else:
    K = (K - v[s]) % l
    print(v.index(K + v[s]))

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

visited = set()
q = deque()
q.append(1)

root = []
while q:
    pos = q.pop()
    if pos in visited:
        start = root.index(pos)
        s_len = len(root[:start])
        l_len = len(root[start:])
        break
    visited.add(pos)
    root.append(pos)

    q.append(A[pos-1])

if K <= s_len:
    print(root[K])
else:
    r = (K - s_len) % l_len
    print(root[start+r])

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = [0] + LI()

visited = [0]*(N+1)  # visited[i] = 町iに何回のテレポートで到着するか
times = [0]*(N+1)  # times[i] = i回目のテレポートでどの町に到着するか
i = 1
a = 0
visited[1] = 0
times[0] = 1
while True:
    i = A[i]
    a += 1
    times[a] = i
    if visited[i] != 0:
        b,c = visited[i],a  # 循環開始、終了
        break
    else:
        visited[i] = a

print(times[K] if K <= a else times[a+(K-a)%(b-a)])

Submission status: Accepted

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

N, K = mapint()
As = list(mapint())

dv = []
for _ in range(K.bit_length() + 1):
    l = [0] * N
    dv.append(l)

dv[0] = list(map(lambda x: x-1, As))

for k in range(1, K.bit_length() + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]

a = []
for i in range(K.bit_length() + 1):
    if (K>>i)&1:
        a.append(i)

now = 0
for i in a:
    now = dv[i][now]
print(now+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
route = [0]
check = {0}
now = 0
while A[now] not in check:
    route.append(A[now])
    check.add(A[now])
    now = A[now]
start = route.index(A[now])
loop = len(route) - start

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,K = MI()
A = [0] + LI()

visited = [0]*(N+1)
times = [0]*(N+1)
i = 1
a = 0
visited[1] = 0
times[0] = 1
while True:
    i = A[i]
    a += 1
    if visited[i] != 0:
        times[a] = i
        b,c = visited[i],a
        break
    else:
        visited[i] = a
        times[a] = i


if K <= a:
    print(times[K])
else:
    print(times[a+(K-a)%(b-a)])

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0];BB=[0]
S = set([]);S.add(0)
now = 0
Flag = False
loop_start = -1
if K <= 2*pow(10,5)+10:
  for i in range(K):
    nxt = A[now]-1
    BB.append(nxt)
    now = nxt
  #print(BB)
  print(BB[K]+1)
  exit()
for i in range(N*2):
  nxt = A[now]-1
  #print(now,nxt)
  if nxt in S:
    if Flag:
      if nxt == loop_start:
        #print(nxt,i)
        loop_cycle = i-loop_num
        break
    else:
      loop_start = nxt
      loop_num = i
      B.append(nxt)
      #print(loop_num,loop_start,B)
      Flag = True
  else:
    B.append(nxt);S.add(nxt)
  now = nxt
loop_num += 1-loop_cycle
#print(B,loop_start,loop_cycle,loop_num)
loc = (K-loop_num)%loop_cycle+loop_num
#print(loc)
#print(len(B))
print(B[loc]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[-1]+list(map(int,input().split()))
dp=[-1]*(n+1)
now=1
cnt=0
while True:
    nex=a[now]
    cnt+=1
    if dp[nex]!=-1:
        break
    dp[nex]=cnt
    now=nex

loop_start=nex
loop=[loop_start]
loop_now=loop_start
loop_next=-1
while loop_start!=loop_next:
    loop_next=a[loop_now]
    loop.append(loop_next)
    loop_now=loop_next
del loop[-1]
if dp[loop_start]>=k:
    print(dp.index(k))
else:
    d=k-dp[loop_start]
    print(loop[d%len(loop)])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

A = [int(x) - 1 for x in input().split()]

cur = 0
step = 0
d = defaultdict(int)
d[0] = step
li = []
while True:
    cur = A[cur]
    li.append(cur)
    if d[cur] != 0:
        break
    step += 1
    d[cur] = step

pre = li[:d[cur]]
loop = li[d[cur]:]

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

Submission status: Accepted

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

a=[None]+[int(i) for i in input().split()]

circle=[1]
for i in range(n):
    circle.append(a[circle[-1]])

def get_head_double(circle):
    check=[0]*(n+1)
    for i in circle:
        check[i]+=1
    for i in circle:
        if check[i]>=2:
            ans=i
            break
    ans_list=[]
    while len(ans_list)<2:
        for i,j in enumerate(circle):
            if j==ans:
                ans_list.append(i)
    return ans_list

ans_list=get_head_double(circle)
circle_front=circle[:ans_list[0]]
circle_back=circle[ans_list[0]:ans_list[1]]

if len(circle_front)>k:
    print(circle_front[k])
else:
    k=k-len(circle_front)
    print(circle_back[k%len(circle_back)])

Submission status: Accepted

Solution code:
def resolve():
    N, K = list(map(int, input().split()))
    A = list(map(lambda x: int(x)-1, input().split()))
    routes = [0]
    current = 0
    visited = [False for _ in range(N)]
    visited[0] = True
    while visited[A[current]] is False:
        current = A[current]
        routes.append(current)
        visited[current] = True
    leftlen = routes.index(A[current])
    repeat = routes[leftlen:]
    # print(leftlen)
    # print(routes)
    # print(repeat)
    print(repeat[(K-leftlen)%len(repeat)]+1 if K > leftlen else routes[K]+1)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[1]
C=["#"]*N
roop=False
for i in range(K):
    if C[B[i]-1]=="#":
        C[B[i]-1]="$"
    else:
        roop=True
        break
    B.append(A[B[i]-1])
if roop==True:
    f=B.index(B[i])
    T=i-f
    if T==0:
        print(B[f])
    else:
        r=(K-f)%T
        print(B[f+r])
else:
    print(B[K])

Submission status: Accepted

Solution code:
from sys import exit
N,K = map(int,input().split())
town = [None]+list(map(int,input().split()))

flag = [None]+[0]*N
remain = K
piece = 1
cnt = 1
while remain > 0:
    if flag[town[piece]] != 0:
        q = cnt-flag[town[piece]]
        piece = town[piece]
        remain -= 1
        break
    else:
        piece = town[piece]
        flag[piece] = cnt
        remain -= 1
        cnt += 1

if remain == 0:
    print(piece)
    exit(0)

remain %= q

while remain > 0:
    piece = town[piece]
    remain -= 1

print(piece)

Submission status: Accepted

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

A = [-1] + A

loop_pos = None
loop_start_time = None
loop_end_time = None
visited = [-1]*(N+1)
pos = 1
i = 0
while visited[pos] == -1:
    visited[pos] = i
    pos = A[pos]
    i += 1  
    if visited[pos] != -1:
        loop_pos = pos
        loop_start_time = visited[pos]
        loop_end_time = i

# print(loop_start_time, loop_end_time)
w = loop_end_time - loop_start_time
K = min(K, loop_start_time) + max(0, K-loop_start_time)%w
# print(f"K: {K}")

pos = 1
for i in range(K):
    # print(pos)
    pos = A[pos]
print(pos)

Submission status: Accepted

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

def main():
    n, k = input_list()
    a = input_list()
    d = {1: 0}
    pre = 1
    loop_start = 0
    loop_end = 0
    loop_pos = 0
    for i in range(1, n+1):
        new = a[pre - 1]
        if d.get(new):
            loop_start = d[new]
            loop_end = i
            loop_pos = new
            break
        if i == k:
            print(new)
            exit()
        d[new] = i
        pre = new
    k -= loop_start
    k %= loop_end - loop_start
    pre = loop_pos
    for i in range(k):
        pre = a[pre - 1]
    print(pre)

    # goto = [a[0]]
    # index = 0
    # looped = []
    # g = 0
    # for i in range(k):
    #     g = goto[index]
    #     # print(goto)
    #     if a[g-1] in goto:
    #         # print("goto!", a[g-1], goto)
    #         break
    #     goto.append(a[g-1])
    #     index += 1
    #
    # s = goto.index(a[g-1])
    # looped = goto[s:]
    #
    # if k % len(looped) == 0:
    #     print(goto[-1])
    # else:
    #     k -= len(goto) - len(looped)
    #     amari = k % len(looped)
    #     print(looped[amari-1])

#6 5 2 5 3 2
#1 2 3 4 5 6

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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

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

flag = 0
done = [0] * (N + 1)

root = []
ind = 0

ind = A[0]
root = [1]
done[1] = 1

while True:

    if done[ind]:
        flag = 1
        break
    done[ind] = 1

    root += [ind]
    ind = A[ind-1]

if flag:
    if len(root) <= K:
        left = root.index(ind) - 1
        loopcnt = len(root) - (root.index(ind))

        root2 = root[left+1:]
        print(root2[(K-(left+1)) % loopcnt])
    else:
        print(root[K])
else:
    print(root[K-1])

Submission status: Accepted

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

loop = []
mark = ['t'] *n
i = 0
loop.append(1)
mark[0] = 0
while True:
  if mark[lst[i]-1] != 't':
    start = mark[lst[i]-1]
    last = mark[i]
    break
  else:
    mark[lst[i]-1] = mark[i] + 1
    loop.append(lst[i])
  i = lst[i]-1
  
  
loop_len = last - start +1
loop_num = loop[start:last+1]
first = start-1

if k <= first:
  print(loop[k])
else:
  q = (k-first) % loop_len
  print(loop_num[q-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [-1 for i in range(N+1)]
B[1] = 0
n = 1
m = 0
while 1:
  n = A[n]
  m += 1
  if m == K:
    print(n)
    break
  if B[n] == -1:
    B[n] = m
  else:
    a = (K - m) % (m - B[n])
    for i in range(a):
      n = A[n]
    print(n)
    break

Submission status: Accepted

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

orb = [1]
counter = [-1] * (N + 1)
v = A[1]
counter[1] = 0
c = 0
while 1:
    c += 1
    if counter[v] == -1:
        counter[v] = c
        orb.append(v)
        v = A[v]
    else:
        break

L = c - counter[v]
T = counter[v]

if K < c:
    ans = orb[K]
else:
    ans = orb[(K - T) % L + T]

print(ans)

Submission status: Accepted

Solution code:
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
routes = [0]
visited = [False] * N
visited[0] = True
now = 0
while True:
    next_town = A[now] - 1
    if visited[next_town]:
        routes.append(next_town)
        break
    visited[next_town] = True
    routes.append(next_town)
    now = next_town
for i, r in enumerate(routes):
    if r == routes[-1]:
        loop = copy.deepcopy(routes[i:])
        break
routes.pop()
loop.pop()
if len(routes) > K:
    print(routes[K] + 1)
else:
    K -= len(routes)
    K %= len(loop)
    print(loop[K] + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  N,M=map(int,input().split())
  L=list(map(int,input().split()))
  i=1
  R=list()
  p=set()
  for j in range(N+1):
    if j==M-1:
      print(L[i-1])
      exit()
    if L[i-1] in p:
      c=R.index(L[i-1])
      t=len(R)-c
      m=R[c:]#ループ
      break
    R.append(L[i-1])
    p.add(L[i-1])
    i=L[i-1]
  l=(M-c-1)%t
  print(m[l])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #今まで行った町（最初も含む）のリスト
dsts = set(dst) #今まで行った町（最初も含む）のset
twn = 1 #テレポーター転送先
for _ in range(k):
    if a[twn - 1] in dsts: #テレポーター転送先が今まで行った町setに入っていたら（そこから先の転送はループする）
        index = dst.index(a[twn - 1]) #今まで行った町リストでのテレポーター転送先のindex取得
        ld = len(dst[:index]) #ループする前の長さとループ部分の周期を求める
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
    else: #テレポーター転送先が今まで行った町setに入っていなかったら
        dst.append(a[twn - 1]) #入っていなかったら今まで行った町リストに追加
        dsts.add(a[twn - 1])
        twn = a[twn - 1] #テレポーター転送先の更新
print(dst[-1])

Submission status: Accepted

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

now=0
visited=set()
visited.add((0))
visited2=[0]


while True:
  k-=1
  now=a[now]-1

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

  
  if now in visited:
    visited.add((now))
    visited2.append(now)
    break

  visited.add((now))
  visited2.append(now)


xxx=visited2[-1]
cnt=[]
for i in range(len(visited2)):
  if visited2[i]==xxx:
    cnt.append(i)


k%=cnt[1]-cnt[0]


if k!=0:
  for i in range(k):
    now=a[now]-1
  

print(now+1)

Submission status: Accepted

Solution code:
# import itertools
# import math
import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, K = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

A.insert(0, 0)
cnt = [0] * (N + 1)

j = 1
times_s = 0
times_e = 0
cycle = 0
for i in range(N + 1):
    if i == K:
        print(j)
        sys.exit()
    cnt[j] += 1
    if cnt[j] == 2:
        times_e = i
        cycle = j
        break
    j = A[j]

j = 1
for i in range(N + 1):
    if j == cycle:
        times_s = i
        break
    j = A[j]

#print(A, cnt)

#print(times_s, times_e, cycle)

K_eff = (K - times_s) % (times_e - times_s)

for i in range(N + 1):
    if i == K_eff:
        print(j)
        sys.exit()
    j = A[j]

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
a = list(map(int, input().split()))
flg = [True] * n
dst = [1]
twn = 0
for _ in range(k):
    if flg[twn]:
        dst.append(a[twn])
        flg[twn] = False
        twn = a[twn] - 1
    else:
        index = dst.index(a[twn])
        ld = len(dst[:index])
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
print(dst[-1])

Submission status: Accepted

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

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

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

d = li.index(num)
ans = (k-d)%(len(li)-d)+d
print(li[ans]+1)

Submission status: Accepted

Solution code:
def abc167d_teleporter():
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    cnts = [0] * (n + 1)
    i = 1
    nxt = 1
    while True:
        if cnts[a[nxt]] == 0:
            cnts[a[nxt]] = i
        else:
            val = (k - i) // (i - cnts[a[nxt]])
            k -= val * (i - cnts[a[nxt]])
        if i == k:
            break
        i += 1
        nxt = a[nxt]
    print(a[nxt])



abc167d_teleporter()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
A=[i-1 for i in A]
seen=[-1]*n;seen[0]=0

cnt=0
now=0
roop=[0]
while 1:
    if seen[A[now]]!=-1:
        roopnum=cnt-seen[A[now]]+1
        mae=seen[A[now]]
        trueroop=roop[seen[A[now]]: cnt+1]
        #print(trueroop,roopnum,mae)
        break
    now=A[now]
    cnt+=1
    roop.append(now)
    seen[now]=cnt

if k<=mae:
    print(roop[k]+1)
else:
    print(trueroop[(k-mae)%roopnum]+1)

Submission status: Accepted

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

visited = [False for _ in range(N)]
visited[0] = True
pattern = [0]
x = 0
start = 0
patternBegin = 0
while True:
    x = A[x]
    if visited[x]:
        patternBegin = x
        break
    pattern.append(x)
    visited[x] = True

# print(pattern)
patternBeginIndex = pattern.index(patternBegin)
beforeLoop = pattern[0:patternBeginIndex]
repeat = pattern[patternBeginIndex:]
# print(beforeLoop, repeat)

if len(pattern) > K:
    print(pattern[K]+1)
else:
    ans = repeat[(K - len(beforeLoop))%len(repeat)]
    # print(pattern)
    print(ans+1)

Submission status: Accepted

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

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

    visited = [False] * N
    visited[0] = True

    index = 0
    visited_index = [0]

    while K:
        index = A[index]
        if visited[index]:
            K -= 1
            start = visited_index.index(index)
            loop_index = visited_index[start:]
            print(loop_index[K % len(loop_index)] + 1)
            sys.exit()
        visited_index.append(index)
        visited[index] = True
        K -= 1
    print(index + 1)
    
main()

Submission status: Accepted

Solution code:
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


_,k = LI()
a = LI()

a = list(map(lambda x:x-1,a))

# 訪れる順序、indexは移動回数
route = [0]
# 訪れた番号、高速検索用にhash tableを使う
visited = set([0])
next = a[0]

while True:
    if next in visited:
        loopStart = route.index(next)
        break
    else:
        route.append(next)
        visited.add(next)
        next = a[next]

# print(route)
# print(loopStart)

beforeLoop = route[:loopStart]
# print(beforeLoop)
loop = route[loopStart:]
# print(loop)

# loop前
if k < loopStart:
    ans = beforeLoop[k]
# loop後
else:
    numOfLoops,mod = divmod((k-(loopStart)),len(loop))
    # print(numOfLoops,mod)
    ans = loop[mod]

ans += 1
print(ans)

Submission status: Accepted

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

current = 0
d = dict()
d[current] = d.get(current, 0) + 1
pattern = [0]
cnt = K

while True:
    current = A[current]
    if d.get(current) == 2:
        break
    else:
        if d.get(current) == None:
            d[current] = d.get(current, 0) + 1
        else:
            d[current] = d.get(current) + 1
        pattern.append(current)
        cnt -= 1
        if cnt == 0:
            break

if cnt == 0:
    print(pattern[-1]+1)
else:
    loop = len([key for key, value in d.items() if value == 2])
    not_loop = len([key for key, value in d.items() if value != 2])
    pattern = pattern[not_loop:]
    ans_position = (K - not_loop) % loop

    print(pattern[ans_position]+1)

Submission status: Accepted

Solution code:
# 一度同じ場所についたら、そこからのループ回数をもう一度求める方法でやってみる
import sys
n,k = map(int,input().split())
a_ls = list(map(int, input().split()))
for i in range(n):
    a_ls[i] -= 1
town_done = [0] * n

# 初期状態のセット
now_town = 0
times = 0
while True:
    # きたtownに関する処理
    town_done[now_town] = 1
    
    # 次の移動
    now_town = a_ls[now_town]
    times += 1
    if times == k:
        print(now_town+1)
        sys.exit()
    if town_done[now_town]:
        base = now_town
        break

rest = k - times
times = 0
while True:
    now_town = a_ls[now_town]
    times += 1
    rest -= 1
    if now_town == base:
        times_per_loop = times
        break
    if rest == 0:
        print(now_town+1)
        sys.exit()

rest = rest % times_per_loop
for _ in range(rest):
    now_town = a_ls[now_town]
print(now_town+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
arr = list(map(int, input().split()))
l = [-1]*(n+1)  # 何回目にそれぞれの頂点に到達したか
tmp = []  # 頂点の移動経路
pos = 1  # 初期位置
cnt = 0  # 移動回数
while 1:
    if l[pos] != -1:  # ある頂点に2回到達したとき
        t = cnt-l[pos]  # ループの長さ
        if k < cnt:
            print(tmp[k])
        else:  # 経路の長さより大きいとき、2回到達した頂点を始点として、最終的にループのどの頂点に到達するかを求める
            print(tmp[l[pos]+(k-cnt) % t])
        break
    l[pos] = cnt
    cnt += 1
    tmp.append(pos)
    pos = arr[pos-1]

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    seen = [False for _ in [0] * (2 * 10 ** 5 + 1)]
    now = 0
    for _ in range(K):
        if seen[now]:
            loop_start = way.index(now)
            loop = way[loop_start:]
            K -= len(way[:loop_start])
            now = loop[K % len(loop)]
            break
        way.append(now)
        seen[now] = True
        now = A[now]
    print(now + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
i=l=1
l=0
F=[0]*n
L=[]
while 1:
  i=A[i-1]
  if F[i-1]>0:
    break
  else:
    L.append(i)
    F[i-1]=l
    l+=1
print((L[F[i-1]:])[(k-F[i-1])%(l-F[i-1])-1] if k>F[i-1] else L[k-1])

Submission status: Accepted

Solution code:
"TLE"

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

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

A_dir_list = []
A_visit_list = [-1 for i in range(N)]
dir = 0

while True:
    A_dir_list.append(dir)
    A_visit_list[dir] = 1
    if A_visit_list[A_list[dir]-1] == -1: 
        dir = A_list[dir]-1
    else:
        cycle_pos = A_dir_list.index(A_list[dir]-1)
        break

if K < cycle_pos:
    print(A_dir_list[K]+1)

else:
    cnt = (K-cycle_pos)%(len(A_dir_list)-cycle_pos)
    print(A_dir_list[cnt+cycle_pos]+1)

Submission status: Accepted

Solution code:
import math

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

# 二次元配列作成
dv = []
for _ in range(int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)

# dv[0][0:N]を初期化。1回目にいるところ
dv[0] = [a-1 for a in A]

# ダブリングで表を構築。2^n回目にいるところを埋める
for k in range(1, int(math.log2(K)) + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]

# bitの立っている位置のみを取得
a = []
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        a.append(i)

now = 0
for i in a:
    now = dv[i][now]
print(now + 1)

Submission status: Accepted

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

A.insert(0,0)

start = 1
next_ = A[1]

visited = [0] * (N+1)
visited[start] = 1

route = [1]
cnt = 0
while True:
    if visited[next_] == 1:
        break
    visited[next_] = 1
    route.append(next_)
    cnt += 1
    if cnt >= K:
        print(next_)
        exit()
    next_ = A[next_]

roop_s = route.index(next_)
roop = route[roop_s:]

stop = (K - roop_s) % len(roop) + 1
ans = roop[stop-1]

print(ans)

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
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1

t2=len(l)-t1
if k<=t1:
    print(l[k])

else:
    aa=(k-t1)%t2
    print(l[t1+aa])

Submission status: Accepted

Solution code:
_, k = map(int, input().split())
a = list(map(int, input().split()))
d = {1: 0}

k += 1
next = 1
cnt = 1
flg = True
while cnt < k:
    next = a[next - 1]
    if flg and next in d:
        flg = False
        d_next = d[next]
        loop_cnt = cnt - d_next  # 1ループの回数
        k -= ((k - d_next) // loop_cnt - 2) * loop_cnt
    d[next] = cnt
    cnt += 1
print(next)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
point=1
m,l=0,0#mは循環する町の数、lはそれまでの町の数
if K>N:
    for i in range(N):
        if B[point-1]==0:
            B[point-1]=i+1
            point=A[point-1]
        else:
            m=i+1-B[point-1]
            l=B[point-1]
            break
    if m!=0:
        m=(K-l)%m
    else:
        m=N
else:
    m=K
ans=1
for i in range(l+m):
    ans=A[ans-1]

print(ans)