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=[int(aa)-1 for aa in input().split() ]

now=0

been = [0]*n
been[0]=1
for i in range(n):
    now=a[now]
    if been[now]==0:
        been[now]=1
    else:
        t_stack=sum(been)
        break

start=now

been = [0]*n
been[now]=1
for i in range(n):
    now=a[now]
    if been[now]==0:
        been[now]=1
    else:
        period=sum(been)
        break

        
if k<=t_stack:
    now=0
    for i in range(k):
        now=a[now]
    print(now+1)
    
else:
    n_itr = (k-t_stack+period)%period
    now=start
    for i in range(n_itr):
        now=a[now]
    print(now+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
# ループを見つけるプログラム？
found = set()
current = 1
log = []
while current not in found:
    found.add(current)
    log.append(current)
    current = a[current - 1]
for i, _log in enumerate(log):
    if (current == _log):
        loop_start = i
        loop_len = len(log) - i
        break
# len(found) * n回移動するとcurrentに移動する
# print('loop_len', loop_len)
# print('loop_start', loop_start)
# print(log[1:])

if (k < loop_start):
    print(log[k])
else:
    k = k - (loop_start)  # ループの先頭へ
    k = k % (loop_len)  # ループを実施
    print(log[loop_start+k])

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()))

    visited = [False] * N
    visited[0] = True
    path = [1]
    loop_s_idx = -1
    loop_e_idx = -1
    a = 1
    while True:
        a = A[a - 1]
        if visited[a - 1]:
            loop_s_idx = path.index(a)
            loop_e_idx = len(path) - 1
            break
        else:
            visited[a - 1] = True
            path.append(a)

    if K < len(path):
        ans = path[K]
    else:
        loop_length = loop_e_idx - loop_s_idx + 1
        q, r, = divmod(K - loop_s_idx, loop_length)
        ans = path[loop_s_idx + r]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,k=n1()
a=[0]
a.extend(n1())

from collections import deque
p=deque([1])
nex=1
town=[0]*(n+1)
town[1]=1
for i in range(n+1):
    last=nex
    nex=a[last]
    p.append(nex)
    if town[nex]==1:
        break
    else:
        town[nex]=1
p.pop()
first=p.index(nex)
length=len(p)
if k<length:
    print(p[k])
else:
    print(p[(k-first)%(length-first)+first])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# import numpy as np
# from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

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

a = [False] * len(A)
now = 1
arrive_list = []

while True:
    arrive_list.append(now)
    if a[now-1]:
        break
    else:
        a[now-1] = True
    now = A[now-1]

r = arrive_list.index(now)
K -= r

if K <= 0:
    print(arrive_list[K+r])
    exit(0)

K %= (sum(a)-r)
print(arrive_list[K+r])

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,k=map(int, readline().rstrip().split())
    aa=list(map(int, readline().rstrip().split()))
    p=0

    if k<n:
        for i in range(k):
            p=(aa[p]-1)
        print(p+1)
        return

    memo=[-1]*n
    memo[0]=0
    for i in range(n*2):
        p=(aa[p]-1)
        if memo[p]==-1:
            memo[p]=i+1
        else:
            diff=(i+1)-memo[p]
            re=k-i-1
            re=re%diff
            for j in range(re):
                p=(aa[p]-1)
            print(p+1)
            return


    #re=k%n
    #for i in range(re):
    #    p=(aa[p]-1)
    #print(p+1)



    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x, cnt):
  if visited[x-1] != -1:
    return [x, visited[x-1], cnt-visited[x-1]]
  else:
    visited[x-1] = cnt
    return tami(a[x-1], cnt+1)

def nasu1(x, cnt):
  if cnt == K:
    return x
  else:
    return nasu1(a[x-1], cnt+1)

def nasu2(x, cnt):
  if cnt == num:
    return x
  else:
    return nasu2(a[x-1], cnt+1)

N,K = IL()
a = IL()

visited = [-1]*N
i, start, roop = tami(1, 0)
if K <= start:
  print(nasu1(1, 0))
else:
  #print(visited)
  num = (K-start)%roop
  #print(start,roop,num)

  print(nasu2(i, 0))

Submission status: Accepted

Solution code:
from collections import defaultdict

graph = defaultdict(int)
N, K =list(map(int, input().split())) 
arr = list(map(int, input().split()))
for i, v in enumerate(arr):
    graph[i+1] = v

if graph[1] == 1:
    print(1)
    exit()

cnt = 1
cur = graph[1]
# cnt2node -> cnt2node
# node2cnt
cnt2node, node2cnt = defaultdict(int), defaultdict(int)
cnt2node[0], cnt2node[1] = 1, cur
node2cnt[1], node2cnt[cur] = 0, 1
while True:
    cur = graph[cur]
    cnt += 1
    if cur in node2cnt:
        break
    else:
        cnt2node[cnt] = cur
        node2cnt[cur] = cnt
        
first = node2cnt[cur]
if K <= first:
    print(cnt2node[K])
else:
    mod = (K - first) % (cnt - first)
    print(cnt2node[first + mod])

Submission status: Accepted

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

n,k=map(int, input().split())
a=list(map(int, input().split()))
isUsed=[False]*n

path = [1]
#isUsed[0] = True

i = 1
while(True):
    idx = i-1
    if isUsed[idx]: #既に行ったことがある町であれば
        #print("行ったことのある町です")
        #print("i", i)
        start = path.index(i)
        break
    else:
        isUsed[idx] = True
        path.append(a[idx])
        #print(path)
        i = a[idx]


if k >= start:
    #print(start)
    #print(len(path)-1)
    num = len(path) - 1 - start
    lis_mod = path[start:start+num]

    mod = len(lis_mod)

    #print("k-start",k-start)
    tmp = (k-start)%mod
    #print("k-start % mod", tmp)
    print(lis_mod[tmp])
else:
    print(path[k])

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, k = sp()
arr = l()
answer = [1]
s = {1}
index = 1
while True:
    temp = arr[answer[-1]-1]
    if temp in s:
        index = temp
        break
    s.add(temp)
    answer.append(temp)
if k <= len(answer)-1:
    out(answer[k])
    exit()
k -= (len(answer)-1)
temp = answer.index(index)
answer = answer[temp:]
k %= len(answer)
if k == 0:
    k = len(answer)
out(answer[k-1])

Submission status: Accepted

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

ma = [-1] * N
ma[0] = 0
now = 1
ne = 0

hazi = -1
for i in range(K):
    ne = A[ne] - 1
    if ma[ne] >= 0:
        hazi = ma[ne]
        break

    ma[ne] = now
    now += 1

if hazi == -1:
    print(ne + 1)
    exit()

ans = (K - hazi) % (now - hazi)

for i in range(ans):
    ne = A[ne] - 1

print(ne + 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
li = [False] * N
f = True
now = 0
l = []
l2 = [0] * N
i = 0
while f:
    l.append(now)
    li[now] = True
    l2[now] = i
    if li[A[now]]:
        f = False
        num = len(l) - l2[A[now]]
        n = l2[A[now]]
    i += 1
    now = A[now]
k = (K-n) % num
print(l[min(K, n+k)]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
roop=[]
roop_set=set([])

a.insert(0, 0)
s=1
for i in range(k):
    s=a[s]
    if(s not in roop_set):
        roop.append(s)
        roop_set.add(s)
    else:
        s_first=roop.index(s)
        roop=roop[s_first:]
        k-=(s_first+1)
#        print(k,roop,s_first)
        print(roop[k%len(roop)])
        break
else:
#    print(roop,k)
    print(roop[k-1])

Submission status: Accepted

Solution code:
import math,sys
from sys import stdin, stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda:int(input())
li = lambda:list(map(int,input().split()))

def case():
    n,k=li()
    a=li()
    d=defaultdict(int)
    i=0
    d[1]=1
    c=0
    ans=[1]
    while(a[i] not in d):
        d[a[i]]=1
        c+=1 
        ans.append(a[i])
        i=a[i]-1
   # print(i)
    #print(ans)
    if(k<len(ans)):
        print(ans[k%len(ans)])
        return
    for j in range(len(ans)):
        if(ans[j]==a[i]):
            ans=ans[j:]
            k-=j
            break 

    #print(ans,k)
    print(ans[(k)%len(ans)])
    




for _ in range(1):
    case()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lst = list(map(int, input().split()))
lst = [0] + lst
count = [0]*(n+1)
pat1 = 0
now = 1
while True:
  count[now] += 1
  if count[now] == 2:
    break
  now = lst[now]
  pat1 += 1


cur = 1
pat2 = 0
while True:
  if cur == now:
    break
  cur = lst[cur]
  pat2 += 1

    

if k > pat2:
  k -= pat2
  k = k % (pat1-pat2)
  k += pat2
  
now = 1
for i in range(k):
  now = lst[now]
  
print(now)

Submission status: Accepted

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

if k<=n:
	ans = 1
	for i in range(k):
		ans = A[ans]
	print(ans)
	exit()

boucle = 1
vis = [False]*(n+1)
vis[1] = True
x = 1
while not vis[A[x]]:
	x = A[x]
	vis[x] = True
	boucle+=1

last = A[x]
sub = 0
d = 1
while d!=last:
	sub+=1
	d=A[d]
boucle-=sub
# ~ print("last",last)
# ~ print("sub",sub)

k-=sub
reste = k%boucle
ans = last
for i in range(reste):
	ans = A[ans]
	
# ~ print("boucle", boucle)
# ~ print("reste", reste)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
arr = list(map(int, input().split()))
check = [0]*N
index = 0
cnt = 0
while True:
    if cnt == K:
        print(index+1)
        exit()
    if check[index] == 1:
        break
    check[index] = 1
    index = arr[index]-1
    cnt += 1

index2 = 0
first_cnt = 0
while True:
    if index2 == index:
        break
    index2 = arr[index2]-1
    first_cnt += 1

ans_cnt = ((K-first_cnt) % (cnt-first_cnt))+first_cnt
index = 0
cnt = 0
while True:
    if cnt == ans_cnt:
        break
    index = arr[index]-1
    cnt += 1
print(index+1)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().strip()
n,k = map(int,input().split())
a = list(map(int,input().split()))
sala = set([0,a[0]-1])
f = 0
s = a[0]-1
power = 1
length = 1
while f!=s:
    if length==power:
        power*=2
        length=0
        f = s 
    s = a[s]-1
    sala.add(s)
    length+=1
start = len(sala)-length
if k<=start:
    cur = 0 
    while k:
        k-=1
        cur = a[cur]-1
    print(cur+1)
else:
    k-=start 
    k%=length
    f = 0
    s = 0 
    while length:
        s = a[s]-1
        length-=1
    while s!=f:
        s = a[s]-1
        f = a[f]-1
    cur = f 
    while k:
        cur = a[cur]-1
        k-=1
    print(cur+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
visited=[0 for i in range(N)]
visited[0]=1
tour=[1]

while True:
    goto=A[tour[-1]-1]
    tour.append(goto)
    if visited[goto-1]:
        break
    visited[goto-1]=1

#print(tour)
    
before=0
shuuki=1
for i in range(len(tour)):
    if tour[i]==tour[-1]:
        before=i
        shuuki=len(tour)-i-1
        break

#print(before,shuuki)

if K<len(tour):
    print(tour[K])
else:
    K-=before
    K%=shuuki
    print(tour[before+K])

Submission status: Accepted

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

counter=1
now=1
gone_set={1}
gone_list=[1]
place=1
while counter<=K:
    next=A[now]
    place=next
    if next in gone_set:
        start=gone_list.index(next)
        loop=len(gone_list)-start
        last=(K-start)%loop
        place=gone_list[start+last]
        break
    else:
        gone_set.add(next)
        gone_list.append(next)
        now=next
        counter+=1

print(place)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class Solver:

    def __init__(self, n, k, a):
        self.n = n
        self.k = k
        self.a = a
        self.pos = 0 # city id starts from 0 in this code
        self.ticket = k
        self.diary = [False] * n
        self.nostalgia = False
        self.hometown = -1
        self.cycle_size = 0

    def run(self):
        #print('hoge') # debug
        self.pos = 0
        self.diary[0] = True
        while not self.nostalgia:
            #print('self.ticket') # debug
            #print(self.ticket) # debug
            if self.ticket == 0:
                return self.answer()
            self.jump()
        self.count_cycle_size()
        self.ticket = self.ticket % self.cycle_size
        while not self.ticket == 0:
            self.pos = self.a[self.pos]
            self.ticket -= 1
        return self.answer()

    def count_cycle_size(self):
        self.cycle_size = 1
        self.pos = self.a[self.pos]
        while not (self.pos == self.hometown):
            self.pos = self.a[self.pos]
            self.cycle_size += 1

    def jump(self):
        self.ticket -= 1
        self.pos = self.a[self.pos]
        if self.diary[self.pos]:
            self.nostalgia = True
            self.hometown = self.pos
        self.diary[self.pos] = True

    def answer(self):
        # rearrange city id to starts from 1
        return self.pos + 1


def make_to_city_id_starts_from_0(a):
    for i, v in enumerate(a):
        a[i] = v - 1

if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    make_to_city_id_starts_from_0(a)

    #print('fuga') # debug
    ans = Solver(n, k, a).run()
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

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

l=[1]
s=set(l)
for i in range(k):
    x=a[l[i]-1]
    if x in s:
        break
    else:
        l.append(x)
        s.add(x)

b=l.index(x)
c=len(l)-b
print(l[((k-b)%c)+b])

Submission status: Accepted

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

mv = 0
i = 1
B = [1]
visit = [0]*N
visit[0] = 1
while True:
    i = A[i-1]
    mv += 1
    B.append(i)
    if mv == K:
        break
    elif visit[i-1] == 1:#ループ処理
        st = B.index(i)
        sa = mv - st
        break
    visit[i-1] = 1
        
if mv == K:
    print(i)
else:
    print(B[st + (K-st)%sa])

Submission status: Accepted

Solution code:
import bisect
import collections
import heapq
import math
import operator as op
from collections import Counter
from functools import reduce

import numpy as np


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def main():

    N, K = get_inputs(int)
    As = get_inputs(int)
    As = [None, ] + As

    prev = 1
    history = {}
    history[1] = 0
    for n_teles in range(1, K+1):
        cur = As[prev]
        if cur in history:
            # Returned to start
            len_cyc = n_teles - history[cur]
            # print("len_cyc: ", len_cyc)
            # print("K - n_teles: ", K- n_teles)
            for _ in range((K - n_teles) % len_cyc):
                cur = As[cur]
            print(cur)
            return
        else:
            prev = cur
            history[cur] = n_teles
    print(cur)

# def main():
#     N, M, X = get_inputs(int)
#     Cs = np.empty(N, dtype=np.int)
#     A_mat = np.empty((N, M), dtype=np.int)
#     for i in range(N):
#         CAs = get_inputs(int)
#         Cs[i] = CAs[0]
#         for j in range(M):
#             A_mat[i, j] = CAs[j+1]

#     if (np.sum(A_mat, axis=0) >= X).all():
#         ans = float("inf")


#     else:
#         print(-1)


#     # N, M, X = get_inputs()
#     # CAs_arr = []
#     # for _ in range(N):
#     #     CAs = get_inputs(int)
#     #     CAs_arr.append(CAs)

#     # Sums = [0 for _ in range(M)]
#     # for i in range(M):
#     #     for j in range(N):
#     #         Sums[i] += CAs_arr[j][i+1]

#     # if all([Sum >= X for Sum in Sums]):
#     #     pass
#     # else:
#     #     print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

i=0
s=1
way=[1]
co={1:[0]}
while  1==1:
    i+=1
    way.append(a[s-1])
    if a[s-1] not in co:
        co[a[s-1]]=[i]
    else:
        if k<co[a[s-1]][0]:
            print(way[k])
            break
        else:
            print(way[co[a[s-1]][0]+(k-co[a[s-1]][0])%(i-co[a[s-1]][0])])
            break
    s=a[s-1]

Submission status: Accepted

Solution code:
import sys

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

alr = {}
now = 1
i = 0
while not now in alr.keys():
    alr[now] = i
    now = A[now-1]
    i += 1
    if i == K:
        print(now)
        sys.exit()

place = alr[now]
circle = len(alr) - place
rem = (K - place) % circle
for k, v in alr.items():
    if v == place + rem:
        print(k)
        break

Submission status: Accepted

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

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

cnt, town = 0, 1
l, s = [], set()
while True:
    town = a[town - 1]
    cnt += 1
    if cnt == k:
        print(town)
        exit()
    if town in s:
        loop_start = town
        break
    l.append(town)
    s.add(town)


loop_cnt = l.index(loop_start)
loop = l[loop_cnt:]
print(loop[(k - loop_cnt) % len(loop) - 1])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[-1]+A
still=[0]*(N+1)
still[1]=1
before=1
rS=-1
root=[1]
while True:
  dest=A[before]
  if still[dest]==1:
    rS=dest
    break
  else:
    still[dest]=1
    root.append(dest)
    before=dest
#print(root,rS)
num=0
for i in root:
  if i==rS:
    break
  num+=1
#print(num)
if K<=num:
  print(root[K])
else:
  K-=num
  root2=root[num:]
  print(root2[K%len(root2)])

Submission status: Accepted

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

check = [0] * (n+10)
res = []
next = 0

for i in range(k):
    if check[next] == 0:
        check[next] = 1
        next = li[next]-1
    elif check[next] == 1:
        check[next] += 1
        res.append(next+1)
        next = li[next]-1
    else:
        cnt = len(res)
        k -= check.count(1)
        amari = k%cnt
        print(res[amari])
        break
else:
    print(next+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
A = li()
flag = [0]*N
l = []
i = 1
ind = 0
while True:
    flag[ind] = i
    l.append(ind+1)
    if not flag[A[ind]-1]:
        ind = A[ind]-1
    else:
        ind = A[ind]-1
        break
    i += 1

if K <= flag[ind] - 1:
    print(l[K])
    exit()

if ind != 0:
    K -= flag[ind] -1
    i -= flag[ind] -1
    l = l[flag[ind] -1:]
print(l[K%i])

Submission status: Accepted

Solution code:
n,k= map(int, input().split())
a= list(map(int, input().split()))
a=[0]+a
x=[0]*(n+1)
s=a[1]
x[1]=1
v1=[1]
cnt1=1
v2=[]
cnt2=0
for i in range(10**7):
    if x[s]==0:
        x[s]+=1
        cnt1+=1
        v1.append(s)
        s=a[s]

    elif x[s]==1:
        cnt2+=1
        x[s] += 1
        v2.append(s)
        s = a[s]
    else:
        break

if k<cnt1:
    print(v1[k])
else:
    q=(k-cnt1)%cnt2
    print(v2[q])

Submission status: Accepted

Solution code:
def task(n, k, a):
    cache = [0] * (n + 1)
    pos = 1
    sequence = [1]
    cache[1] = pos
    index = 1
    prefix = 0
    ks = k

    while True:
        index += 1
        nxt = a[pos - 1]

        if cache[nxt] != 0:
            prefix = cache[nxt] - 1
            cycle = sequence[prefix:]
            break

        sequence.append(nxt)
        cache[nxt] = index
        pos = nxt

        ks -= 1

        if ks == 0:
            print(nxt)
            return

    target = (k - prefix) % len(cycle)
    print(cycle[target])


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, K = read_ints()

A = read_ints()
B = []
for a in A:
    B.append(a - 1)

# ループするまで回してみる?
# 閉路が知りたい
# 閉路の起点をメモ
# K←（K-起点までの回数）
# K%閉路の長さ
# のこりは愚直に起点から再スタート

nums_to_arrive = [-1] * N
nums_to_arrive[0] = 0
now = 0
while True:
    to = B[now]
    if nums_to_arrive[to] == -1:
        nums_to_arrive[to] = nums_to_arrive[now] + 1
        if nums_to_arrive[to] == K:
            print(to + 1)
            exit()
    else:
        break
    now = to
n1 = nums_to_arrive[to]
n2 = nums_to_arrive[now] + 1 - n1
base = to  # 起点
# print(base)


K = (K - n1) % n2  # 残り移動回数
# print(n1, n2, K)
now = base  # 起点をもとに開始する
while K:
    to = B[now]
    K -= 1
    now = to
print(now + 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(lambda x: int(x)-1,input().split()))
towns = [0]
added = [-1] * n
added[0] = 0
for i in range(1,k+1):
    tmp = a[towns[-1]]
    pl = added[tmp]
    if pl != -1:
        loop = towns[pl:]
        last = (k-pl) % len(loop)
        print(loop[last]+1)
        exit()
    else:
        added[tmp] = i
        towns.append(tmp)
print(towns[-1]+1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
# stdin = open("sample.txt")

MOD = 1000000007

def keta(kazu):
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def combination(m,n):
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def main():
    n, k = [int(x) for x in stdin.readline().rstrip().split()]
    a_1 = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    a_2 = [0] + [0] * (n-1)
    a_3 = []
    now = 1
    while True:
        now = a_1[now-1]
        a_3.append(now)
        if a_2[now-1]:
            break
        else:
            a_2[now-1] = 1
    start = a_3.index(a_3[-1])
    a_4 = a_3[:start]
    a_5 = a_3[start:-1]
    if k <= len(a_4):
        print(a_4[k-1])
    else:
        amari = k - len(a_4)
        # print(a_1,a_2,a_3,a_4,a_5)
        print(a_5[(amari%len(a_5))-1])

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
tlist = list(map(int, input().split()))
check = [1]*n
town = 1
loop =[]
while bool(check[town-1]):
  check[town-1] = 0
  loop.append(town-1)
  town = tlist[town-1]
init = loop.index(town-1)
if k < init:
  print(loop[k]+1)
else:
  print(loop[init+(k-init)%(len(loop)-init)]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
cnt=[]
m=0
ans=0
for i in range(2*n):
  if a[m] in d:
    ans+=1
    cnt.append(a[m])
    if ans==k:
      print(a[m])
    break
  else:
    d[a[m]]=0
    cnt.append(a[m])
    ans+=1
    if ans==k:
      print(a[m])
      break
    m=a[m]-1
if ans!=k:
  if cnt[-1]==cnt[-2]:
    print(cnt[-1])
  else:
    cnt=cnt[cnt.index(cnt[-1]):-1]
    print(cnt[(k-ans)%len(cnt)])

Submission status: Accepted

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

#閉路を検知する

visitted = [-1] * n
cur_town = 0
town_cnt = 0
visitted[0]=town_cnt
town_cnt+=1
while True:
    next_town = a[cur_town]
    if visitted[next_town]==-1:
        visitted[next_town]=town_cnt
        town_cnt+=1
        cur_town=next_town
    else:
        break

last_move = (k-town_cnt)%(town_cnt-visitted[next_town])
if k < town_cnt:
    print(visitted.index(k)+1)
else:
    cur_town=next_town
    for _ in range(last_move):
        next_town = a[cur_town]
        cur_town=next_town
    print(cur_town+1)

Submission status: Accepted

Solution code:
import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

n,k = Ri()
a = Ri()
a= [0]+a
ans = []
# ans.append(0)
dic = {}
prev = 1
# dic[0] = 0
ite  = 0
flag = -1
for i in range(n):
    if a[prev] not in dic:
        ans.append(a[prev])
        dic[a[prev]] = ite
        prev = a[prev]
        ite+=1
    else:
        flag = a[prev]
        break
start = dic[flag]
# print(ans,dic)
if k-1 < start:
    print(ans[k-1])
else:
    # print(start,ans)
    cyclen = len(ans)-start
    k-=1
    k -= start
    k%=cyclen
    print(ans[start+k])

Submission status: Accepted

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

Submission status: Accepted

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

step = 0
init_loop = 0
interval = 0
state = 1
visited = [-1]*(n+1)
visited[1] = 0
for i in range(1,3*n):
    state = a[state]
    if i == k:
        print(state)
        exit()
    if visited[state] >= 0:
        init_loop = visited[state]
        interval = i - init_loop
        break
    visited[state] = i

mod = (k - init_loop) % interval
for idx,v in enumerate(visited):
    if v == mod +init_loop:
        print(idx)
        exit()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


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

    pos = A[1]
    visited = {1}
    while pos not in visited:
        visited.add(pos)
        pos = A[pos]
    
    start = pos
    loop = 1
    pos = A[pos]
    while pos != start:
        pos = A[pos]
        loop += 1
    
    dist = 0
    pos = 1
    while pos != start:
        pos = A[pos]
        dist += 1

    #print("dist={}, loop={}".format(dist, loop))
    
    if dist < K:
        K -= dist
        K %= loop
        pos = start
        for _ in range(K): pos = A[pos]
        print(pos)
    else:
        pos = 1
        for _ in range(K): pos = A[pos]
        print(pos)


if __name__ == "__main__":
    main()