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:
import numpy as np 
import sys 

readline = sys.stdin.readline

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

# 愚直にやると計算量O(K)でTLEになる
# 同じ街にいったら操作打ち切りで配列を完結させる

# Teleport順の配列を作る
teleport = {1: True}
next_town = 1
roop_exist = False
for i in range(K):
    next_town = A[next_town - 1] # next_townがintで与えられる
    try: # 辞書を使用してO[1]で判定する
        teleport[next_town]
        dupulicate_town = next_town
        # 辞書をリストに変換
        teleport = list(teleport.keys())
        dupulicate_index = teleport.index(dupulicate_town)
        dupulicate_list = teleport[dupulicate_index:]
        roop_exist = True
        break
    except KeyError:
        teleport[next_town] = True


# 最後の処理の前にリストに変換してしまう
if not roop_exist:
    teleport = list(teleport.keys())

if len(teleport) - 1 == K:
    print(teleport[-1])
else: # ループに入る場合
    consumption = len(teleport) - 1
    roop_num = K - consumption
    roop_index = roop_num % len(dupulicate_list)
    if roop_index == 0:
        print(dupulicate_list[-1])
    else:
        print(dupulicate_list[roop_index - 1])

Submission status: Accepted

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

route = []
town = set()
now = 1

while True:
    now = a[now-1]
    if now in town:
        break
    town.add(now)
    route.append(now)

count = route.index(now)
if count >= k:
    print(route[k-1])
else:
    route = route[count:]
    num = (k-count)%len(route)
    print(route[num-1])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town_check =[False]*(N+1)
already_town_check[1] = True
already_town = [1]
now_town=1
check=False
my_append = already_town.append
for i in range(K):
    check_town=A[now_town-1]
    if(already_town_check[check_town]):
        cicle_start_value=check_town
        check=True
        break
    already_town_check[check_town]=True
    my_append(check_town)
    now_town = check_town

if(check==False):
    print(now_town)
else:
    cicle_start=already_town.index(cicle_start_value)
    roop_town=already_town[cicle_start:]
    print(roop_town[(K-cicle_start)%((i+1)-cicle_start)])

Submission status: Accepted

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

now = 0
goal,loop,visit = [],[],[0]*N

while visit[now]!=2:

  if visit[now]==0:
    goal.append(now)
  else:
    loop.append(now)
    
  visit[now] += 1
  now = tele[now]-1

if len(goal)>K:
  print(goal[K]+1)
else:
  res= len(goal)-len(loop)
  print(loop[(K-res)%len(loop)]+1)

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
    
visited = [-1] * n
now = 0

for i in range(k):
    if visited[now] != -1:#訪れたことがあるか
        loop = i - visited[now]   #ループの大きさ
        k = (k-(i-loop)) % loop
        
        for _ in range(k):
            now = a[now]
        
        break
        
    visited[now] = i
    now = a[now] 
        
print(now + 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()))
    B = [1]
    a = 1
    check = [0] * len(A)
    while True:
        a = A[a - 1]
        if check[a - 1] == 1:
            x = B.index(a)
            roop = B[x:]
            print(roop[(K - x) % len(roop)])
            exit()
        B.append(a)
        check[a - 1] += 1
        if len(B) >= K + 1:
            print(B[K])
            exit()
if __name__ == '__main__':
    main()

Submission status: Accepted

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

genzaiti=1
otozure=[-1]*(10**6)
hantei=True

otozure[1]=0
houmon=0
idou_kaisuu=0

while k>0:
    idou_kaisuu+=1
    k-=1
    genzaiti=a[genzaiti]

    if hantei:
        if otozure[genzaiti]!=-1:
            kaiten=idou_kaisuu-otozure[genzaiti]
            k%=kaiten
            hantei=False
    
    otozure[genzaiti]=idou_kaisuu

print(genzaiti)

Submission status: Accepted

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

i = 0
check = [True]*b
his = []
n = 0
his.append(0)
while(1):
    #print(his)
    i = a[i] - 1
    if check[i]:
        check[i] = False
        his.append(i)
    else:
        n = len(his)-his.index(i)
        break
m = len(his) - n
p = 0
if k > m:
    p = (k-m)%n + m
else:
    p = k
i = 0
#print(n,m,p)
for j in range(p):
    #print(a[i])
    i = a[i] - 1
print(i+1)

Submission status: Accepted

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

r = []
check = [0]*len(a)
now = 1
count = 0

while True:
    r.append(now)
    now = a[now - 1]
    
    if check[now - 1] == 1:
        roop = r[r.index(now):]
        break
    check[now - 1] += 1
    
if len(r) - 1 >= k: #ループに入らないとき
    print(r[k])
else:#ループに入ったとき
    print(roop[(k-len(r)) % len(roop)])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(i)-1 for i in input().split()]
def times(X,Y):
    return [X[Y[i]] for i in range(N)]
def exponen(X,n):
    if n==0:
        return [i for i in range(N)]
    if n==1:
        return X
    if n%2==0:
        Y=exponen(X,n//2)
        return times(Y,Y)
    if n%2==1:
        Y=exponen(X,n//2)
        return times(times(Y,Y),X)
B=exponen(A,K)
print(B[0]+1)

Submission status: Accepted

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

tele_lst = []
town_set = set()
town = 1
while True:
  if town not in town_set:
    tele_lst.append(town)
    town_set.add(town)
  else:
    break
  town = lst[town - 1]
ind = tele_lst.index(town)
length = len(town_set)
circle = length - ind
#print(ind, length)
#print(tele_lst)
if k < ind:
  town = tele_lst[k]
  print(town)
else:
  k -= ind
  k %= circle
  #print(k)
  town = tele_lst[ind + k]
  print(town)

Submission status: Accepted

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


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

  non_loop_time = 0
  loop_time = 0
  time = [0]*(N+1)
  stack = [1]
  visited = set()
  visited.add(1)
  t = 0
  root = [1]

  while len(stack):

    t += 1
    now = stack[-1]
    time[now] = t
    next_ = A[now-1]

    if next_ not in visited:
      root.append(next_)
      visited.add(next_)
      stack.append(next_)
    else:
      non_loop_time = time[next_] - 1
      loop_time = time[now] - time[next_] + 1
      break

  if K <= non_loop_time:
    print(root[K])
  else:
    K -= non_loop_time
    K %= loop_time
    print(root[non_loop_time+K])


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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
B = []
j = 1
for i in range(n):
    B.append(j)
    j = A[j-1]
    
visited = [-1] * (n+1)
cs = -1
i = 1
count = 0
while True:
    visited[i] = count
    count += 1
    i = A[i-1]
    if visited[i] != -1:
        cs = i
        break
#print (count, count-visited[cs], cs, visited[cs])
if k < n:
    print(B[k])
    exit()
cl = count - visited[cs]
a =(k-visited[cs]) % cl
current = cs-1
for i in range(a):
    current = A[current] -1
print(current+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
l=[1]
X=[True]*N
X[0]=False
num=1
for i in range(K):
    num=A[num-1]
    if X[num-1]:
        l.append(num)
        X[num-1]=False
    else:
        q=l.index(num)
        l=l[q:]
        print(l[(K-q)%len(l)])
        exit()
print(l[-1])

Submission status: Accepted

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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    Acnt = [0] * N
    Acnt[0] = 1
    telepo = [1]
    i = 0
    while True:
        Acnt[A[i] - 1] += 1
        if Acnt[A[i] - 1] > 1:
            break
        telepo.append(A[i])
        i = A[i] - 1
    roop_s = telepo.index(A[i])
    roop = len(telepo) - roop_s

    ans = 0
    if K < roop_s:
        ans = K
    else:
        ans = K - roop_s
        ans %= roop
        ans += roop_s

    print(telepo[ans])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
c=[0]*(n+1)
c[1]=1
q=[0,1]
while True:
  i=a[q[-1]]
  if c[i]:break
  c[i]=c[q[-1]]+1
  q+=[i]
if c[i]<k:
  k-=c[i]-1
  t=c[q[-1]]-c[i]+1
  print(q[c[i]+k%t])
else:print(q[k+1])

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
b = list(map(int, input().split()))
a=0
for i in range(n):
    b[i] -= 1
if k<n:
    for i in range(k):
        a = b[a]
    print(a+1)
    exit()
c = [-1]*n
cc = 0
se = set()
while a not in se:
    c[a] = cc
    cc += 1
    se.add(a)
    a = b[a]
for i in range((k-c[a])%(cc-c[a])):
    a = b[a]
print(a+1)

Submission status: Accepted

Solution code:
# カウントと踏破フラグをもっておくと二度目の踏破でループの長さが分かりそう

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
count_arr = [0] * n
count = 0

now = 0
loop_length = -1
while True:
    if count == k:
        print(now + 1)
        exit()
    if count_arr[now] != 0:
        loop_length = count - count_arr[now] + 1
        break
    count += 1
    count_arr[now] = count
    now = a[now]

# 真の残り回数
rest = (k - count) % loop_length

# 既にゴールしてると見る場合
if rest == 0:
    print(now + 1)
    exit()

while rest > 0:
    rest -= 1
    if rest == 0:
        break
    now = a[now]
print(a[now] + 1)
# 727202214173249352

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,k=I()
a = l()
town = []
num = [0]*(n+1)
cnt = 1
num[0]=1

for i in range(n):
    num[a[cnt-1]] += 1
    if num[a[cnt-1]] == 2:
        ans = a[cnt-1]
        p = town.index(ans)
        b = town[p:]
        x = len(town)
        y = len(b)
        q = k-x+y
        if y == 0:
            print(town[n-1])
            sys.exit()
        if q < 0:
            print(town[k-1])
            sys.exit()
        z = q%y
        print(b[z-1])
        sys.exit()
        break
    town.append(a[cnt-1])
    cnt = a[cnt-1]

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,k=I()
a = l()
town = []
num = [0]*(n+1)
cnt = 1
num[0]=1

for i in range(n):
    num[a[cnt-1]] += 1
    if num[a[cnt-1]] == 2:
        ans = a[cnt-1]
        p = town.index(ans)
        b = town[p:]
        x = len(town)
        y = len(b)
        q = k-x+y
        if y == 0:
            print(town[n-1])
            sys.exit()
        if q < 0:
            print(town[k-1])
            sys.exit()
        z = q%y
        if z == 0:
            print(town[z-1])
        else:
            print(b[z-1])
        sys.exit()
        break
    town.append(a[cnt-1])
    cnt = a[cnt-1]

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] + [int(x) for x in stdin.readline().rstrip().split()]

m = 0
b = [1]
visited = [-1 for i in range(n+1)]

c = 1
visited[1] = 1
for i in range(n):
    c = a[c]
    if visited[c] != 1:
        b.append(c)
        visited[c] = 1
        if i == k-1:
            print(c)
            sys.exit()
    else:
        break

idx = b.index(c)
bn = len(b[idx:])
sn = len(b[:idx])

# print(b,idx,sn,bn)
kk = (k-sn) % bn
print(b[idx+kk])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
N,K=map(int, sys.stdin.readline().split())
A=[None]+map(int, sys.stdin.readline().split())
visit=[ 0 for _ in range(N+1) ]

L=[]    #閉路になった町番号を順番に記録する

def func(fro):
    global K
    to=A[fro]
    visit[fro]+=1
    if visit[fro]==2:
        L.append(fro)
    if visit[to]<=1:    #閉路ループは2回まで許可する
        K-=1        #操作回数を減らす
        if K==0:    #Kが途中でゼロになれば、その時に移動しようとしていたtoが答え
            print to
            quit()
        func(to)

func(1)
K-=1
l=len(L)
print L[K%l]

Submission status: Accepted

Solution code:

def solve():
    n,k=map(int,input().split())
    a=[-1]+list(map(int,input().split()))

    stp=[-1]*(n+1)

    vis=1
    stp[1]=0
    while k >= 0 :
        if k==0 :
            return vis
        nxt=a[vis]
        if stp[nxt] == -1 :
            stp[nxt]=stp[vis]+1
            vis=nxt
            k-=1
        else:
            loop=stp[vis]+1-stp[nxt]
            k%=loop
            for i in range(0,k) :
                vis=a[vis]
            return vis

print(solve())

Submission status: Accepted

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

A_={}
for a_idx,a in enumerate(A):
    A_[a_idx+1] = a

visit={}
first={}
for n in range(N):
    visit[n+1]=0
    first[n+1]=-1
    
v=1
Loop=[]
for n in range(2*N):   
    Loop.append(v)
    if visit[v] == 0:
        first[v] = n
    visit[v]+=1
#     print(v,visit)
    if visit[v] == 2:
        break
        
    v=A_[v]

if K-first[v] < 0:
    print(Loop[K])
else:  
    ans_idx=(K-first[v])%(n-first[v])
    print(Loop[first[v]:n][ans_idx])

Submission status: Accepted

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

s = []
o = [-1] * (n + 1)
count = 0

v = 1
while o[v] == -1:
    o[v] = count
    s.append(v)
    v = a[v-1]
    count += 1

l = o[v]
c = len(s) - o[v]
    
if k < l:
    print(s[k])
else:
    k -= l
    k = k % c
    print(s[l+k])

Submission status: Accepted

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

b = 0
r = k + 1
seen = [-1] * n
seen[0] = 0
p = 1
for i in range(k):
    p = a[p - 1]
    if seen[p - 1] != -1:
        b = seen[p - 1]
        r = i + 1 - b
        for j in range((k - b) % r):
            p = a[p - 1]
        print(p)
        exit()
    seen[p - 1] = i + 1
else:
    print(p)

Submission status: Accepted

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

def tortoise_and_hare(s,f):
    tortoise = f[s]
    hare = f[f[s]]

    while tortoise != hare:
        tortoise = f[tortoise]
        hare = f[f[hare]]

    rho = 0
    tortoise = s
    while tortoise != hare:
        tortoise = f[tortoise]
        hare = f[hare]
        rho += 1

    lamb = 1
    hare = f[hare]

    while tortoise != hare:
        hare = f[hare]
        lamb += 1

    return rho,lamb

rho, lamb = tortoise_and_hare(0,f)

if k <= rho:
    s = 0
    for i in range(k):
        s = f[s]
else:
    s = 0
    for i in range(rho):
        s = f[s]
    k = (k-rho)%lamb
    for i in range(k):
        s = f[s]

print(s+1)

Submission status: Accepted

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

import sys
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


seen = defaultdict(list)
count = 0
pos = 0
seen[pos].append(count)

while True:
    pos = A[pos]
    count += 1
    seen[pos].append(count)
    if len(seen[pos]) == 2:
        head = seen[pos][0]
        loop = count - head
        break


if K < head:
    pos = 0
    for i in range(K):
        pos = A[pos]
    print(pos+1)


else:
    K = K - head
    res = K % loop
    for i in range(res):
        pos = A[pos]

    print(pos+1)

Submission status: Accepted

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

#A1から順にワープした時の経由順
now = 0
goal,loop,visit = [],[],[0]*N

while visit[now]!=2:

  if visit[now]==0:
    goal.append(now)
  else:
    loop.append(now)
    
  visit[now] += 1
  now = tele[now]-1

if len(goal)>K:
  print(goal[K]+1)
else:
  amari = len(goal)-len(loop)
  print(loop[(K-amari)%len(loop)]+1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
dist = [-1] * n

i = 0
dist[0] = 0
while True:
    nxt = a[i] - 1
    if dist[nxt] >= 0:
        if k > dist[nxt]:
            k -= dist[nxt]
            k %= dist[i] - dist[nxt] + 1
            k += dist[nxt]
        print(dist.index(k) + 1)
        break
    dist[nxt] = dist[i] + 1
    i = nxt

Submission status: Accepted

Solution code:
def f():
    n,k=map(int,input().split())
    l=list(map(int,input().split()))
    now=1
    for d in range(k.bit_length()):
        k,f=divmod(k,2)
        if f:now=l[now-1]
        l=tuple(l[i-1]for i in l)
    print(now)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
def f():
    n,k=map(int,input().split())
    l=list(map(int,input().split()))
    now=1
    for d in range(k.bit_length()):
        if k%2:now=l[now-1]
        l=tuple(l[i-1]for i in l)
        k//=2
    print(now)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
def f():
    n,k=map(int,input().split())
    l=list(map(int,input().split()))
    now=1

    for i in range(k.bit_length()):
        if k%2:now=l[now-1]
        l=tuple(l[l[i]-1]for i in range(n))
        k//=2
    print(now)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
def f():
    n,k=map(int,input().split())
    l=list(map(int,input().split()))
    now=1

    for i in range(k.bit_length()):
        if k%2:now=l[now-1]
        l=[l[l[i]-1]for i in range(n)]
        k//=2
    print(now)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
def f():
    n,k=map(int,input().split())
    l=list(map(int,input().split()))
    now=1

    for i in range(k.bit_length()):
        if k and k%2:now=l[now-1]
        l=tuple(l[l[i]-1]for i in range(n))
        k//=2
    print(now)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
now=1
while k:
    k,f=divmod(k,2)
    if f:now=l[now-1]
    l=[l[l[i]-1]for i in range(n)]
print(now)

Submission status: Accepted

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

c = [0] * (n + 1)

q = [1]

while True:
  p = m[p]
  if (c[p] == 1):
    break
  c[p] += 1
  q.append(p)
i = q.index(p)
q1 = q[:i]
q2 = q[i:]
if len(q1) > 0 and k < len(q1):
  print(q1[k])
else: 
  print(q2[(k - len(q)) % len(q2)])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]



#いまいるところ,
#listとnが与えられたときn回テレポートしたところを出力する
def now_place(li,n):
    now = 1
    for i in range(n):
        now = li[now-1]
    return now

#p回のテレポートでたどってきた道筋のルートを返す

def root(li,p):
    ans = []
    now = 1
    for j in range(p):
        ans.append(now_place(li,j+1))
    return ans



n,k = MI()
a = LI()
#訪れたところのメモがtown
town = []
#訪れたかどうかを0と1で管理
visit=[0]*n
p = 1
while visit[p-1] == 0:
    town.append(p)
    visit[p-1] = 1
    p = a[p-1]
#香りだかい町がいつでてきたか→周期に入るまでのテレポート回数
#len(town[l:])は周期を表す
l = town.index(p)
if k <len(town):
    print(town[k])
else:
    print(town[l + (k-l)%(len(town[l:]))])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]



#いまいるところ,
#listとnが与えられたときn回テレポートしたところを出力する
def now_place(li,n):
    now = 1
    for i in range(n):
        now = li[now-1]
    return now

#p回のテレポートでたどってきた道筋のルートを返す

def root(li,p):
    ans = []
    now = 1
    for j in range(p):
        ans.append(now_place(li,j+1))
    return ans



n,k = MI()
a = LI()
#訪れたところのメモがtown
town = []
#訪れたかどうかを0と1で管理
visit=[0]*n
p = 1
while visit[p-1] == 0:
    town.append(p)
    visit[p-1] = 1
    p = a[p-1]
l = town.index(p)
if k <len(town):
    print(town[k])
else:
    print(town[l + (k-l)%(len(town[l:]))])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

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

    # See:
    # https://www.youtube.com/watch?v=ENSOy8u9K9I&feature=youtu.be
    # KeyInsight:
    # 移動: 周期的ではない + 周期的に繰り返すの合計
    # 実装上のポイント
    # 経路と順番を別々に管理する
    path = list()
    order = [-1 for _ in range(n + 1)]  # -1: 到達していない
    place = 1

    # 到達していない点がある限り、ループを繰り返す
    # = 同じ点を2回通るまで繰り返す
    while order[place] == -1:
        order[place] = len(path)  # ある場所を通った順番を管理
        path.append(place)  # 経路を更新
        place = a[place - 1]  # 次の行き先

    # 周期: 同じ点を2回通るまでに要した移動回数 - 周期に入るまでの移動回数
    cycle = len(path) - order[place]
    before_cycle_count = order[place]

    if (k < before_cycle_count):
        print(path[k])
    else:
        k -= before_cycle_count
        k %= cycle  # 周期: 途中の繰り返し部分を省いて、途中の部分だけ計算するようにする
        print(path[before_cycle_count + k])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    import sys
    input = sys.stdin.readline

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

    # See:
    # https://www.youtube.com/watch?v=ENSOy8u9K9I&feature=youtu.be
    path = list()
    order = [-1 for _ in range(n + 1)]
    place = 1

    while order[place] == -1:
        order[place] = len(path)
        path.append(place)
        place = a[place - 1]

    cycle = len(path) - order[place]
    before_cycle_count = order[place]

    if (k < before_cycle_count):
        print(path[k])
    else:
        k -= before_cycle_count
        k %= cycle
        print(path[before_cycle_count + k])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dis=[-1]*(n+1)
now=1
time=0
while 1 :
    if dis[now]>=0 : break
    dis[now]=time
    time+=1
    now=alst[now]

if time>k :
    print(dis.index(k))
else :
    head=dis[now]
    roop_unit=time-dis[now]
    work=(k-head)%roop_unit
    print(dis.index(head+work))

Submission status: Accepted

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

now = A[0]
root_set = set([now])
root_array = [now]
if k<= n:
    for i in range(k-1):
        now = A[now-1]
        root_set.add(now)
        root_array.append(now)
    print(root_array[-1])
else:
    for i in range(n-1):
        now = A[now-1]
        if not now in root_set:
            root_set.add(now)
            root_array.append(now)
        else:
            index = root_array.index(now)
            f = root_array[:index]
            loop = root_array[index:]
            break
    len_f = len(f)
    len_loop = len(loop)
    print(loop[(k-len_f)%len_loop-1])

Submission status: Accepted

Solution code:

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

dp = [[0] * (N + 1) for _ in range(100)]
dp[0] = [0] + X
for k in range(1, 100):
    for i in range(N + 1):
        dp[k][i] = dp[k - 1][dp[k - 1][i]]

ans = 1
for k in range(100):
    if K >> k & 1:
        ans = dp[k][ans]

print(ans)

Submission status: Accepted

Solution code:
#import time

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    As = [0]+As
    ikisaki = As[1]
    aru = {1}
    itta = [1]
    imaitta = 1
  
    while not ikisaki in aru:
        imaitta = ikisaki
        ikisaki = As[ikisaki]
        itta.append(imaitta)
        aru.add(imaitta)
    ind = itta.index(ikisaki)
    kurikaesi = itta[ind:]
    itidokiri = itta[:ind]
    ans = itidokiri[K] if len(itidokiri) > K else kurikaesi[(K-len(itidokiri))%len(kurikaesi)]


    return ans

if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Accepted

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

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

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

point = 1

dev = [1]
flag = 0

for i in range(1, k + 1):
    if cheak[point]:
        loop = i -cheak[point]
        pre_loop = cheak[point]
        flag = 1
        break
    else:
        cheak[point] = i
        point = a[point]
        #dev.append(point)

if flag:
    rest = (k + 1- pre_loop) % loop
    for j in range(rest):
        point = a[point]
        #dev.append(point)

print(point)

Submission status: Accepted

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

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

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

point = 1

dev = [1]
flag = 0

for i in range(1, k + 1):
    if cheak[point]:
        loop = i -cheak[point]
        pre_loop = cheak[point]
        flag = 1
        break
    else:
        cheak[point] = i
        point = a[point]
        dev.append(point)

if flag:
    rest = (k + 1- pre_loop) % loop
    for j in range(rest):
        point = a[point]
        dev.append(point)

print(point)

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

ans=0
hub_city=0
visited=[-1]*n
now=0
cnt_warp=0
loop_cnt=0
first_visit_hub_city=0

for i in range(n):
    if visited[now]>-1:
        hub_city=now
        first_visit_hub_city=visited[now]
        loop_cnt=cnt_warp-first_visit_hub_city
        break
    else:
        visited[now]=cnt_warp
    
    now=A[now]
    cnt_warp+=1

idoukaizu=min(first_visit_hub_city+(k-first_visit_hub_city)%loop_cnt,k)

now=0
for i in range(idoukaizu):
    now=A[now]

print(now+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x: x - 1, map(int, input().split())))
current = 0
memo = {
    0: 0
}
for i in range(1, K + 1):
    current = A[current]
    if current in memo:
        # loop length
        length = i - memo[current]
        tmp = (K - memo[current]) % length
        for j in range(tmp):
            current = A[current]
        break
    else:
        memo[current] = i
print(current + 1)

Submission status: Accepted

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

if k == 1:exit(print(A[0]))
t = 0
dp = [-1] * n
dp[0] = 0
flg = 0
for i in range(1,k+1):
  t = A[t]-1
  if dp[t] != -1:
    flg = 1
    break
  dp[t] = i
if flg == 0:
  exit(print(t+1))
elif k == 2:
  exit(print(t+1))

l = i - dp[t]
K = (k-dp[t])%l + dp[t]

for i in range(n):
  if dp[i] == K:exit(print(i+1))

Submission status: Accepted

Solution code:
from collections import Counter

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

city=[0]*n
city[0]+=1
dict={}
for x in range(n-1):
  b=city[x]-1
  c=a[b]
  city[x+1]+=c
  
for y in range(n):
  d=city[y]
  e=str(d)
  if e in dict:
    check=d
    end=y
    break
  if  e not in dict:
    dict[e]=y

start=city.index(d)
w=end-start
if k<start:
  print(city[k])
  
else:
  kk=k-start
  rest=kk%w
  q=start+rest
  print(city[q])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
cc = list(map(int,input().split()))
memo = []
aa = ['.']*N
a = 1
while aa[a-1] == '.':
  memo.append(a)
  aa[a-1] = 'v'
  a = cc[a-1]
if len(memo)>K:
  print(memo[K])
else:
  b = memo.index(a)
  m = len(memo)-b
  mm = (K-b) % m
  del memo[:b]
  print(memo[mm])

Submission status: Accepted

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

ls = [-1] * n
now = 0
cnt = 0
path = []
while 1:
    if ls[now] != -1:
        b = ls[now]
        break
    ls[now] = cnt
    path.append(now)
    now = a[now]
    cnt += 1
loop = path[b:]
if k <= b:
    print(path[k] + 1)
else:
    print(loop[(k - b) % len(loop)] + 1)