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 sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n, k = MII()
    aa = MIIZ()
    idx = [-1]*n
    next_t = 0
    idx[next_t] = next_t
    visit = [0]
    loop_flag = False
    for i in range(k):
        next_t = aa[next_t]
        visit.append(next_t)
        if idx[next_t] == -1:
            idx[next_t] = i+1
        else:
            loop_flag = True
            break
    if loop_flag:
        l = visit.index(visit[-1])
        loop = visit[l:-1]
        i = (k-l)%len(loop)
        print(loop[i]+1)
    else:
        print(visit[-1]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.zeros((N), dtype=np.int)
*A[:], = map(int, input().split())
A[:] -= 1 # 0ベースに変更

visited = np.zeros((N), dtype=np.bool)
recent_turn = np.zeros((N), dtype=np.int64)

here = 0
rest_turn = K

while rest_turn > 0:
	if visited[here]:
		# 周回スキップ実装
		interval = recent_turn[here] - rest_turn
		rest_turn %= interval
		if rest_turn == 0:
			break
	else:
		# ソシャゲ周回
		visited[here] = True
	
	recent_turn[here] = rest_turn
	here = A[here]
	rest_turn -= 1

# 1ベースに戻す
print(here + 1)

Submission status: Accepted

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

A = list(map(int,input().split()))
t = 0
c = 0
ans = [0] * n
L = []
s = 0
for _ in range(k):
    if ans[t] == 1:
        n = len(L) - L.index(t)
        temp = (k-c)%n
        t = L[L.index(t):][temp]
        break
    else:
        ans[t] = 1
        L.append(t)
        t = A[t]-1
        c += 1
print(t+1)

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
dest = [int(x) for x in input().split()]
route = [1]
flag = [1] + [0] * (N-1)
t = 1
while True:
  if flag[dest[t-1]-1] == 0:
    t = dest[t-1]
    route.append(t)
    flag[t-1] = 1
  else:
    loop = route.index(dest[t-1])
    L_loop = len(route) - loop
    break
  #print(route)
  #print(flag)
ans = 0
if K < len(route):
  ans = route[K]
else:
  K = K - len(route)
  ans = route[loop + (K % L_loop)]
print(ans)

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split()))
tele = list(map(int, input().split()))
loc = 1
act = [-1]*n
act[0]=0
count = 1
log = []
log.append(loc)
flg = True
while True:
  newloc=tele[loc-1]
  if count ==k:
    print(newloc)
    flg = False
  log.append(newloc)
  #print(newloc)
  if act[newloc-1] == -1:
    act[newloc-1] =count
  else:
    loop=count-act[newloc-1]
    loopstart=act[newloc-1]
    break
  count+=1
  loc=newloc

  

if flg:
  num = (k-loopstart) % loop 
  ans=log[loopstart+num]
  print(ans)

#print(loopstart)
#print(log)
#print(log[loopstart])
#print(num)

Submission status: Accepted

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

rireki = [-1 for i in range(N)]
rireki[0] = 0
ima = 0
kuri = 0
start = 0
end = 0
for i in range(K):
  saki = A[ima]
  if rireki[saki - 1] == -1:
    rireki[saki - 1] = i + 1
    ima = saki - 1
  else:
    ima = saki - 1
    kuri = 1
    start = rireki[saki - 1]
    end = i + 1
    break
    
if kuri == 1:
  KK = (K - start) % (end - start)
  for i in range(KK):
    saki = A[ima]
    ima = saki - 1

print(ima+1)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = [0]+a
bunki = 0
now = a[1]
lip = [1]
se = set()
while True:
    bunki += 1
    if now in se:
        break
    se.add(now)
    lip.append(now)
    now = a[now]

tenki = lip.index(now)
lis = lip[tenki:]
roop = bunki-tenki

if k < tenki: 
    print(lip[k])
    exit()
k -= tenki

print(lis[k%roop])

Submission status: Accepted

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

num_list = [1]
n_set = set([1])
flag = True
while flag:
    tmp = a_list[num_list[-1]-1]
    if tmp in n_set:
        flag = False
    else:
        n_set.add(tmp)
        num_list.append(tmp)
        
idx = num_list.index(tmp)
loop = len(num_list) - idx
if k < idx:
    print(num_list[k])
else:
    print(num_list[(k-idx)%loop  + idx])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = []
for i in range(len(A)):
    B.append(0)

ok = 0
i = 0
cnt1 = 0
cnt2 = 0
B[0] = 1
while ok == 0:
    i = A[i]-1
    if B[i] == 0:
        B[i] = 1
    else:
        ok = 1
        B[i] = 2
    cnt1 += 1
while ok == 1:
    i = A[i]-1
    if B[i] == 1:
        B[i] = 2
    else:
        ok = 2
    cnt2 += 1

if K > cnt1:
    K -= cnt1
    ok = 3
if K > cnt2 and ok == 3:
    K = K % cnt2

if ok == 2:
    i = 0
    
while K > 0:
    i = A[i]-1
    K -= 1

print(i+1)

Submission status: Accepted

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

hush = {}
for i in range(1, n+1):
    hush[i] = 0

loop = []
cur_town = 1
while hush[cur_town] == 0:
    loop.append(cur_town)
    hush[cur_town] = 1
    cur_town = A[cur_town-1]

root = loop.index(cur_town)

if k < root:
    print(loop[k])
else:
    loop_len = len(loop[root:])
    ind = root + (k-root)%loop_len
    print(loop[ind])

Submission status: Accepted

Solution code:
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(n,k,a):
    zan = 0
    count = 0
    p = 1
    t = {i:-1 for i in range(n)}
    t[0] = 0
    for i in range(k):
        count += 1
        p = a[p-1]
        if t[p-1] == -1 :
            t[p-1] = count
        else:
            loop = count - t[p-1]
            zan = (k- t[p-1]) % loop
            break
    for i in range(zan):
        p = a[p-1]
    return p

n,k = mi()
a = mi()
print(main(n,k,a))

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a = list(map(int, input().split()))
t = [0 for i in range(n)]
now = a[0] -1
t[0] = 1
root = [0]
for i in range(0,k):
    if t[now] == 0:
        root.append(now)
        t[now] = 1
        now = a[now] -1
    else:
        break
if len(root)- 1 == k:
    print(root[-1]+1)
else:
    for i in range(0,len(root)):
        if root[i] == now:
            b = len(root) - i
            c = (k-i)%b
            print(root[i+c]+1)

Submission status: Accepted

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x)-1 for x in input().split()]
past = 0
history = [0]
s = set()
while True:
    na = A[past]
    if na in s: 
        break
    s.add(na)
    history.append(na)
    past = na
s = history.index(na)
e = len(history)
loop = e - s
if K <= s: # ループ前終了
    print(history[K]+1)
else:
    k = K - s
    print(history[s+(k%loop)]+1)

Submission status: Accepted

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

t = 0
l = []
c = 0
d = {}
while True:
    d[t+1] = c
    c += 1
    l.append(t+1)
    t = a[t] - 1
    # if t == 0:
    #     break
    if t + 1 in d:
        s = l[d[t+1]:]
        q = d[t+1]
        break
# print(l)
# print(s)
# print(d)
# print(q)

if k <= q:
    print(l[k])
else:
    print(s[(k-q) % len(s)])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
now = 1
flag = [False] * N
c = 0
temp = [0]*N
hoge = False
for i in range(K):
    if flag[now-1]:
        hoge = True
        break
    temp[now-1] = i
    flag[now-1] = True
    now = A[now-1]
    c += 1
if hoge:
    c -= temp[now-1]
    K -= temp[now-1]
    for _ in range(K%c):
        now = A[now-1]
print(now)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict
import collections
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

tf = [False] * (n + 1)
tf[1] = True
ss = [1]
cnt = 0
while cnt < max(k,n ** 2):
    if len(ss) != 1 and tf[a[ss[cnt] - 1]]:
        d = a[ss[cnt] - 1]
        break
    tf[a[ss[cnt] - 1]] = True
    ss.append(a[ss[cnt] - 1])
    cnt += 1

if len(ss) > k:
    print(ss[k])
else:
    sss = ss.index(d)
    print(ss[sss+(k -len(ss)) % (len(ss) - sss)])
    # print(ss.index(d))
    # print(ss[k % (len(ss) - ss.index(d))])

Submission status: Accepted

Solution code:
n , k = map(int, input().split())
a = list(map(int,input().split()))
v = [0]*(n+1)
v[1]=1
v2=[1]
i=0
step=1

while True:
    if v[a[i]]!=0:
        loop=step-v[a[i]]+1
        loopstart=v[a[i]]
        break
    else:
        step+=1
        v[a[i]]=step
        v2.append(a[i])
        i=a[i]-1
ans = (k-loopstart+2)%loop
if ans ==0:
    ans+=loop
if k<loopstart:
    print(v2[k])
    exit()
v2=v2[loopstart-1:]
print(v2[ans-1])

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

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

#################################################
#################################################
#################################################
#################################################



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

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

now = 0
count = 0
route = [0]
done = [-1 for i in range(n)]
done[0]= 0
roopStart = -1
roopLen = -1
while(True):
    now = a[now]
    route.append(now)
    count+=1
    if(done[now]>=0):
        roopStart = now
        roopLen = count - done[now]
        break
    else:
        done[now] = count

        
#print(route,roopStart)
#print(done)

if(k<done[roopStart]):
    #print('a')
    print(route[k]+1)
else:
    #print('b',roopStart, roopLen, done[roopStart])
    #print(route)
    print(1+route[done[roopStart] + (k-done[roopStart])%roopLen])

Submission status: Accepted

Solution code:
def solve(n, k, a):
    ori_k = k

    mapper = {}
    for i in range(n):
        idx = i+1
        to = a[i]
        mapper[idx] = to

    path = [1]
    cur_town = 1
    visited = set()
    visited.add(1)

    before_cycle = None
    while k > 0:
        k -= 1
        cur_town = mapper[cur_town]
        if k == 0:
            return cur_town
        if cur_town in visited:
            before_cycle = path.index(cur_town)
            path = path[path.index(cur_town):]
            break
        
        path.append(cur_town)
        visited.add(cur_town)

    # print(path, len(path))
    # print(before_cycle)
    # print((ori_k-before_cycle) % len(path))
    result = path[(ori_k-before_cycle) % len(path)]
    return result



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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
As = [int(e)-1 for e in input().split()]
visited=[0]*N

town = 0
for k in range(K):
    town = As[town]

    if visited[town] > 0:
        break
    
    visited[town] = k+1

else:
    print(town+1)
    exit()

K = K-visited[town]
K=K%((k+1)-visited[town])


for _ in range(K):
    town = As[town]

print(town+1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
lis = [-1] * len(A)
nex = 1
start = 0
loop = 0
result = -1
for i in range(len(A)):
    if i == K:
        result = nex
    if lis[nex-1] ==-1:
        lis[nex-1]=i
        nex = A[nex-1]
    else :
        start = nex
        loop = i - lis[nex-1]
        break
nex = start
end = (K-lis[start-1])%loop
for i in range(end):
    nex = A[nex-1]
if result ==-1:
    result = nex
print(result)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=set()
new=0
c=0
while not new in visited and c<k:
  visited.add(new)
  new=a[new]-1
  c+=1
if c==k:
  print(new+1)
else:
  start=new
  d=0
  visited=set()
  while not new in visited and d<k-c:
    visited.add(new)
    new=a[new]-1
    d+=1
  if k-c==d:
    print(new+1)
  else:
    new=start
    for i in range((k-c)%d):
      new=a[new]-1
    print(new+1)

Submission status: Accepted

Solution code:
## coding: UTF-8

#ループ構造を見つけたらやめるところまで実装
#freshを用意して、Falseになったらやめる実装

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



#log = [1] #訪れた地点を記録するもの
#last  = 1 #最後に訪れた地点を記録するもの（ここから次に行くところを検索する）
fresh = ['a'] + [True] * N #まだついたことのない場所をTrueにしている
fresh[1] = False
turn = ['a'] + [0] * N #なん回目におとづれたか記録する
status = True



def search_loop():
    log = [1] #訪れた地点を記録するもの
    last  = 1 #最後に訪れた地点を記録するもの（ここから次に行くところを検索する）
    counter = 0
    while status:
        next_spot = A[last - 1]
        counter += 1
        #print(next_spot)
        if(fresh[next_spot]):
            #処理を書く
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            turn[next_spot] = counter
        else:
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            #最後の人処理をする
            break
    return log, last, turn, counter
    



if(A[0] == 1):
    #1から1へテレポートするなら、答えは必ず1になる。
    ans = 1
else:
    loop, loop_folder, kiroku, count = search_loop()
    #print('loop:{}, loop_folder(結節点):{}, kiroku(なん回目にどこを訪れた):{}, count(終わらせた歩数):{}'.format(loop, loop_folder, kiroku, count))
    #print('結節点を最初に通ったのはK={}'.format(kiroku[loop_folder]))
    x = kiroku[loop_folder]
    p = count - x #p歩でループする
    #print(p)
    if(K < x):
        ans = loop[K]
    else:
        l = loop[x:count]
        L = K - x
        mod = L % p
        #print(mod)
        #print(l[mod])
        ans = l[mod]
print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    A_list = [x-1 for x in A_list]

    passed_list = [False] * N
    time_go_same_city = 0
    now_city = 0
    passed_list[now_city] = True
    while True:
        next_city = A_list[now_city]
        if passed_list[next_city]:
            start_circle_city = next_city
            break
        passed_list[next_city] = True
        time_go_same_city += 1
        now_city = next_city

    passed_list = [False] * N
    time_circle_city = 1
    now_city = start_circle_city
    passed_list[now_city] = True
    while True:
        next_city = A_list[now_city]
        if passed_list[next_city]:
            break
        passed_list[next_city] = True
        time_circle_city += 1
        now_city = next_city

    if time_go_same_city >= K:
        num_teleport = 0
        now_city = 0
        while num_teleport < K:
            next_city = A_list[now_city]
            num_teleport += 1
            now_city = next_city
        print(now_city+1)
        return
    
    K -= time_go_same_city
    K %= time_circle_city
    if K == 0:
        K = time_circle_city
    num_teleport = 1
    now_city = start_circle_city
    while num_teleport < K:
        next_city = A_list[now_city]
        num_teleport += 1
        now_city = next_city

    print(now_city+1)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Accepted

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

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

tel_list = []

next_city = 0

city_have_been_to = set([0])

way = [0]

while k > 0:
    k -= 1
    temp = len(city_have_been_to)

    next_city = a[next_city] - 1
    city_have_been_to.add(next_city)
    way.append(next_city)

    if temp == len(city_have_been_to):
        break

if k == 0:
    print(way[-1] + 1)
else:
    temp_index = way.index(next_city)
    print(way[temp_index:-1][k % len(way[temp_index:-1])] + 1)

Submission status: Accepted

Solution code:
# ABC167d


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    pos = [-1] * n
    pos[0] = 0

    nex = a[0] - 1
    now = 0
    turn = 0

    mode = False

    while True:
        if not mode and pos[nex] == -1:
            if turn == k:
                print(now+1)
                exit(0)
            pos[nex] = pos[now] + 1
            now = nex
            nex = a[nex] - 1
            turn += 1
            continue
        if mode:
            if turn == k:
                print(now+1)
                exit(0)
            pos[nex] = pos[now] + 1
            now = nex
            nex = a[nex] - 1
            turn += 1
            continue
        circle = turn - pos[nex] + 1
        turn += (k-turn) // circle * circle
        mode = True

    # print(pos)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1 , input().split()))
b = [0]
z = [-1] * n
idx = 1
z[0] = idx
aloop = True
c = 0
while True:
    c = a[c]
    if z[c] > -1:
        break
    b.append(c)
    idx += 1
    z[c] = idx

#print(b, z, idx, z[c])
# 周期
ll = idx - z[c] + 1
# 切片
dd = z[c] - 1
if k < dd:
    print(b[k]+1)
    exit()
#print(ll, dd)
#print('-', (k - dd) % ll, (k - dd) % ll + dd)
print(b[(k - dd) % ll + dd]+1)

#print(b[k % ll]+1)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=list(map(lambda x:int(x)-1,readline().split()))

    flags=[False]*n

    now=0
    cnt=0
    while True:
        flags[now]=True
        cnt+=1
        nex=a[now]
        if flags[nex]:
            last=now
            break
        else:
            now=nex

    f_cnt=cnt
    cnt=0
    while True:
        nex=a[now]
        if nex==last:
            cnt+=1
            break
        else:
            now=nex
            cnt+=1

    l=k-(f_cnt-cnt)
    if l<0:
        now=0
        for _ in range(k):
            now=a[now]
        print(now+1)
    else:
        l%=cnt
        now=a[last]
        for _ in range(l):
            nex=a[now]
            now=nex

        print(now+1)
if __name__=="__main__":
    main()

Submission status: Accepted

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

    base, cycle = 0, 0
    order = [-1] * N
    order[0] = 0
    cnt = 1
    idx = A[0] - 1
    while True:
        if order[idx] == -1:
            order[idx] = cnt
            cnt += 1
            idx = A[idx] - 1
            continue
        base = order[idx]
        cycle = cnt - order[idx]
        break

    if base + cycle <= K:
        rest = (K - base) % cycle
        ans = order.index(base + rest) + 1
    else:
        ans = order.index(K) + 1
    print(ans)

abc167_d()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
nk = list(map(int,input().split()))
N, K = nk[0], nk[1]

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


if ( N < K ):	# 何周もループする場合
  cur = 1
  count = 0
  A_chk = [0] * len(A)
  
  while ( A_chk[cur-1]==0 ):
    A_chk[cur-1] = 1	# 行ったことのある町をマークする
    cur = A[cur-1]		# 次の町にテレポート
    count += 1			# テレポート回数
    #print(cur)
  #print("count =",count)
  
  loop_s = cur		# ループの起点になる町をマーク
  count_b = count	# ループ終了時のテレポート回数
  
  cur = 1
  count = 0
  while ( cur != loop_s ):
    cur = A[cur-1]
    count += 1
  #print("count =",count)
  
  before_loop_count = count
  loop_count = count_b - count
  #print(before_loop_count,loop_count)
  
  K_re = ( K - before_loop_count ) % loop_count
  #print(K_re)
  
  cur = loop_s
  for i in range(K_re):
    cur = A[cur-1]
  print(cur)
  
else:	# 正攻法
  cur = 1
  for i in range(K):
    cur = A[cur-1]
    #print(cur)
  print(cur)

Submission status: Accepted

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------
import sys
sys.setrecursionlimit(10**6)
from types import GeneratorType
#use:- put @bootstrap overrecursive function
def bootstrap(func, stack=[]):
    def wrapped_function(*args, **kwargs):
        if stack:
            return func(*args, **kwargs)
        else:
            call = func(*args, **kwargs)
            while True:
                if type(call) is GeneratorType:
                    stack.append(call)
                    call = next(call)
                else:
                    stack.pop()
                    if not stack:
                        break
                    call = stack[-1].send(call)
            return call
    return wrapped_function


n,k = mapi()
a = [0]+list(mapi())
gr = defaultdict(int)
for i in range(1,n+1):
    gr[i]=a[i]

vis ={}
path = []
p = 1

@bootstrap
def dfs(s):
    global p
    if s in vis:
        p = s
        yield 0
    path.append(s)
    vis[s] = 1
    res =0
    res+= yield dfs(gr[s])
    yield res
dfs(1)
i = 0
ln = 0
path2 = path[:]
while i<len(path):
    if p==path[i]:
        path2 = path2[i:]
        break
    i+=1
#print(path)
if k<len(path)-len(path2):
    print(path[k])
else:
    k -= len(path)-len(path2)
    print(path2[k%len(path2)])
#print(dfs(1,k))

Submission status: Accepted

Solution code:
pi = 3.1415926

############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n,k = invr()
nums = [0] + inlt()
cycle = [nums[1]]
s = set([cycle[0]])
bp = 0
for i in range(2*n):
    if nums[cycle[-1]] not in s:
        s.add(nums[cycle[-1]])
        cycle.append(nums[cycle[-1]])
        
    else:
        bp = nums[cycle[-1]]
        break

if k <= len(cycle):
    print(cycle[k - 1])
else:
    if bp != 0:
        for i in range(len(cycle)):
            if cycle[i] == bp:
                cycle = cycle[i:]
                break
    k -= i
    remain = k % len(cycle)
    print(cycle[remain - 1])

Submission status: Accepted

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

hant = [0 for i in range(n)]
add = [1]
now = 1
hant[0]= 1
count = 1
for i in range(max(n,k)):
    now = A[now-1]
    add.append(now)
    #print(now)
    count+=1
    if hant[now-1] == 0:
        hant[now-1] = count
    else:
        syuki = count-hant[now-1]
        amari = hant[now-1]-1
        break

rep = add[amari:syuki+amari]

#print(syuki,amari,add,rep)

if k>=amari:
    ind = (k-amari)%syuki
    print(rep[ind])
elif k<amari:
    print(add[k])

Submission status: Accepted

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

ans=[]
judge={}
j=0 #A進み
while A[j] not in judge.keys() or judge[A[j]]!=2:
    ans.append(A[j])
    if A[j] not in judge.keys():
        judge[A[j]]=0
    judge[A[j]]+=1
    j=A[j]-1

st=ans.index(A[j])

if st<K:
    ans=ans[st:]
    K-=st
    l=len(ans)
    #print(ans)
    print(ans[K%l-1])
else:
    print(ans[K-1])

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, k =MAP()

a = LIST()

# vis = [False]*n
# idx = 0
# temp = [a[0]-1]
# vis[a[0]-1] =True
i=0
j = 1
dd = defaultdict(int)
dd[1] = 0
while(True):
    if(a[i] in dd):
        pos = dd[a[i]]
        break
    dd[a[i]] = j
    i = a[i]-1
    j+=1

suited = list(dd.keys())[pos:]
temp = j-pos
if(k>=pos):
    k-=pos
    k = k%temp

    print(suited[k])
else:
    newS = list(dd.keys())[:pos]
    print(newS[k])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
town = [-1]*N
i=1
n=0
while True:
    if town[i-1] == -1:
        town[i-1] = n
        i = a[i-1]
    else:
        roop = i
        break
    n += 1

amari = (K-town[roop-1])%(n-town[roop-1])
if K-town[roop-1]>0:
    print(town.index(town[roop-1]+amari)+1)
else:
    print(town.index(K)+1)

Submission status: Accepted

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

list=[-1]*n
list[1-1]=0 #町1は0ばんめ

p=1
count=0
end=False

while True:
    count+=1
    p=A[p-1]
    if count==k:
        end=True
        break

    if list[p-1]==-1:
        list[p-1]=count
    else:
        loop=count-list[p-1]
        break

if end==False:
    count+=loop*(((k-count)//loop)-1)
    while True:
        count+=1
        p=A[p-1]
        if count==k:
            end=True
            break

print(p)

Submission status: Accepted

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

town = 0
visited = [town]
index = 0
visited_index = {town: index}
loop = None
while K > 0:
    K -= 1
    town = A[town]
    if town in visited_index:
        loop = visited[visited_index[town]:]
        break
    visited.append(town)
    index += 1
    visited_index[town] = index

if loop:
    K %= len(loop)
    print(loop[K]+1)
else:
    print(town+1)

Submission status: Accepted

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

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

graph = []

time = [-1] * N

now = 0
nex = 0
time[0] = 0
loop = 0

while True:
    now = nex
    nex = A[now] - 1

    if time[nex] == -1:
        time[nex] = time[now] + 1
    else:
        loop = nex
        break

if K > max(time):
    K -= time[loop]
    K %= (max(time) - time[loop] + 1)
    tmp = time[loop]
    for i in range(N):
        time[i] -= tmp

for i in range(N):
    if time[i] == K:
        print(i + 1)

# print(time, K)