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 = [0] + list(map(int, input().split()))

before=k
roop=1
cnt={}
nxt=1
mp = [1]
for i in range(1, k+1):
    if nxt not in cnt:
        cnt[nxt] = i
        nxt = a[nxt]
    else:
        roop = i - cnt[nxt]
        before = cnt[nxt]-1
        break
    mp.append(nxt)
print(mp[before + (k-before)%roop])

Submission status: Accepted

Solution code:
import sys

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [0] + A
town = 1
visited = [0]*(N+1)

for i in range(1, K+1):
    town = A[town]
    if visited[town] == 0:
        visited[town] = i
    else:
        loop = i - visited[town]
        place = (K - visited[town]) % loop + visited[town]
        print(visited.index(place))
        sys.exit()
print(town)

Submission status: Accepted

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

# N = [7, 8]
# A = [3, 2, 4, 5, 6, 4, 2]
A = [A[k]-1 for k in range(N[0])]

L = [0]*N[0]
p = 0
t = 0
L[0] = 1
for k in range(N[1]):
    if L[A[p]] == 0:
        L[A[p]] = k+2
        p = A[p]
    else:
        t = 1
        break

if t == 0:
    print(p+1)
else:
    loop = L[p]-L[A[p]]+1
    stop = (N[1]-L[p]+1) % loop

    for k in range(stop):
        p = A[p]
    print(p+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
class Doubling:
    def __init__(self, lst, max_step):
        self.lst = lst
        self.max_step = max_step
        self.k = int(log2(max_step * 2 - 1)) + 1
        # print(self.k)
        self.D = self.create()

    def create(self):
        len_ = len(self.lst)
        D = [[-1] * len_ for _ in range(self.k)]
        D[0] = self.lst
        d = 2
        for i in range(1, self.k):
            for j in range(len_):
                D[i][j] = D[i - 1][D[i - 1][j]]
            d *= 2
        # print(D)
        return D

    def step(self, start, step):
        v = start
        for i in range(self.k, -1, -1):
            l = 1 << i
            if l <= step:
                v = self.D[i][v]
                # print(i, l)
                step -= l
        return v

def solve():
    N, K = MI()
    A = LI1()

    db = Doubling(A, K)
    v = db.step(0, K)
    print(v+1)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

rireki = [0] * (2 * 10 ** 5 + 1)
flag = [[] for _ in range(2 * 10 ** 5 + 1)]
rireki[0] = 1
flag[1].append(0)
count = 0
roop_start = 0
roop_count = 0
while True:
    count += 1
    rireki[count] = a[rireki[count - 1] - 1]
    flag[rireki[count]].append(count)
    if len(flag[rireki[count]]) == 2:
        roop_start = flag[rireki[count]][0]
        roop_count = flag[rireki[count]][1] - flag[rireki[count]][0]
        break
    if count == K:
        break
if roop_count != 0:
    print(rireki[(K - roop_start) % roop_count + roop_start])
else:
    print(rireki[K])

Submission status: Accepted

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

field = [(i, j) for i, j in zip(range(n), list(map(int, input().split())))]

#%%
town = 0 # 町は1始まりだが、indexの都合上-1する
order = 0 # 訪問順序
visited = {town: order} # 訪問済みの街を格納

while True:
    trans = field[town][1] - 1 # 現在のtownにあるテレポーターの移動先
    n_town = field[trans][0] # 遷移先の町. これはリストのindexになってるので-1しなくてよい
    if n_town not in visited.keys():
        order += 1
        visited[n_town] = order  # 訪問済みにする
    else: # 訪問済みを踏んだ時 TODO この実装だとループ内の数が数えられない
        st_circ = visited[n_town]
        break
    town = n_town

#%%
# ループ開始前まで
vk = list(visited.keys())
mae = len(vk[:st_circ])
circ = len(vk[st_circ:])

if k < mae:
    ans = vk[k]
else:
    idx = (k - mae) % circ
    ans = vk[idx + mae]

print(ans+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(x)-1 for x in input().split()]
B=[0]
visited=[False]*N
for g,here in enumerate(B):
	if visited[here]:
		break
	visited[here]=True
	B.append(A[here])
s=B.index(here)
r=(K-s)%(g-s)
ans=B[s:][r]+1 if K>=s else B[K]+1
print(ans)

Submission status: Accepted

Solution code:


#input = sys.stdin.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] +A  #transporter
    visited = [0] * (N+1)
    town = 1
    cycle = 0
    for i in range(1,K+1):
        town = A[town]
        if visited[town] ==0:
            visited[town] = i
        else:
            cycle = i - visited[town]
            place = (K - visited[town]) % cycle + visited[town]
            print(visited.index(place))
            exit()
    print(town)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict



#input = sys.stdin.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] +A  #transporter
    visited = [0] * (N+1)
    town = 1
    cycle = 0
    for i in range(1,K+1):
        town = A[town]
        if visited[town] ==0:
            visited[town] = i
        else:
            cycle = i - visited[town]
            place = (K - visited[town]) % cycle + visited[town]
            print(visited.index(place))
            exit()
    print(town)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict



#input = sys.stdin.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] +A  #transporter
    visited = [0] * (N+1)
    town = 1
    cycle = 0
    for i in range(1,K+1):
        town = A[town]
        if visited[town] ==0:
            visited[town] = i
        else:
            cycle = i - visited[town]
            place = (K - visited[town]) % cycle + visited[town]
            for j in range(N+1):
                if visited[j] == place:
                    print(j)
                    exit()
    print(town)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

    tele_num = 0
    check = [0]*(N+1)
    check[1] = 1
    temp = 1
    i = 2
    roop_num = 0
    sho = 0
    amari = 0

    while i != K+2:
        temp1 = A[temp-1]
        if check[temp1] != 0:
            roop_num = check[temp] - check[temp1] + 1
            tele_num = K + 2 - i - 1
            sho = tele_num // roop_num
            amari = tele_num % roop_num
            break

        check[temp1] = i
        i += 1
        temp = temp1

    #print(roop_num,tele_num,sho,amari)

    j = 0
    temp = temp1
    while j != amari:
        temp1 = A[temp-1]
        #check[temp1] = i
        j += 1
        temp = temp1

    print(temp)
    #print(i,temp, check)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    n, k = rl()
    A = rl()
    # leaps = [A]
    # leap_size = 2
    # while leap_size <= k:
        # new_leap = []
        # for i in range(n):
    curr = 1
    seen = {1:0}

    for i in range(1, k + 1):
        curr = A[curr - 1]
        if i == k:
            print (curr)
            return
        elif curr in seen:
            break
        seen[curr] = i

    cycle_len = i - seen[curr]
    # print (cycle_len)

    while 1:
        if i % cycle_len == k % cycle_len:
            print (curr)
            return
        i += 1
        curr = A[curr - 1]






mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Accepted

Solution code:
from collections import deque

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

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

mati = deque([1])
mark = set([1])
tugi = 1
for i in range(1, k+1):
    if tere[tugi] not in mark:
        mati.append(tere[tugi])
        mark.add(tere[tugi])
    else:
        mati.append(tere[tugi])
        mark.add(tere[tugi])
        break
    tugi = tere[tugi]
else:
    print(tugi)
    exit()

mati = list(mati)
cnta = len(mati)-1
i = mati.index(mati[-1]) + 1
cntroop = cnta - i + 1
roop = mati[i:]

print(roop[(k-cnta)%cntroop-1])

Submission status: Accepted

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

while b[v] == -1:
    b[v] = len(s)
    s.append(v)
    v = a[v]-1
    
c = len(s) - b[v]
l = b[v]

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

Submission status: Accepted

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

r = []
f = [-1]*N
now = 0
loop = 0

i = 0


while i < K:
    r.append(now)
    f[now] = i
    now = A[now]
    i += 1
    if f[now] >= 0:
        loop = i-f[now]
        nokori = K-i
        print(r[f[now]+nokori%loop]+1)
        break
else:
    print(now+1)

Submission status: Accepted

Solution code:
import sys
import itertools

n, k = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
a_len = len(a) - 1

b = [1]
labeled = set(b)
index = 1
loop_start = 0
while len(labeled) <= a_len:
  p = a[index - 1]
  if p in labeled:
    loop_start = b.index(p)
    break
  labeled.add(p)
  b.append(p)
  index = p
#print(f'{b=}')
#print(f'{loop_start=}')

loop_len = len(b) - loop_start
#print(f'{loop_len=}')

if k < len(b) - 1:
  print(b[k])
else:
  kk = k - loop_start
  # print(f'{kk=}')
  kk %= loop_len
  # print(f'{kk=}')
  kk += loop_start
  # print(f'{kk=}')

  print(b[kk])

Submission status: Accepted

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

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
  #print(t_zero,a)
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  a = a = t_zero.index(t_zero[a-1] + k) + 1
print(a)

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
    N,K = map(int,input().split())
    A = list(input().split())
    current_p = 0
    loop_length = 0
    loop_start = 0
    Nlist = - np.ones(N, dtype = int)
    Nlist[0] = 0
    for i in range(1, min(N + 1,K + 1)):
        next_p = int(A[current_p]) - 1
        if Nlist[next_p] == -1:
            current_p = next_p
            Nlist[next_p] = i
        else:
            loop_start = Nlist[next_p]
            loop_length = i - loop_start
            break
    if loop_length != 0:
        ans =  loop_start + (K - loop_start) % loop_length
    else:
        ans = K 
    print(np.where(Nlist == ans)[0][0] + 1)
resolve()

Submission status: Accepted

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

seen = [False] * (n+1)
visited = []
nxt = 1
cnt = 0
while not seen[nxt] and cnt != k:
    seen[nxt] = True
    visited.append(nxt)
    nxt = a[nxt]
    cnt += 1

if cnt == k:
    print(nxt)
    exit()
    
idx = visited.index(nxt)
print(visited[idx:][(k-idx)%(len(visited)-idx)])

Submission status: Accepted

Solution code:
'''
path = 'sub1_51.txt'
f=open(path)
data1 = f.read()
f.close()
N=data1.split()
'''
n,k=map(int,input().split())
A=list(map(int,input().split()))
'''
n=int(N[0])
k=int(N[1])
A=N[2:]
'''
A=[int(i)-1 for i in A]
B=[]
cnt=[0]*n
m=0
for i in range(2*10**5):
    B.append(m)
    cnt[m]+=1
    if cnt[m]>1:
        break
    m=A[m]
c=len(B)-(B.index(m)+1)
print(1+B[(max(k-B.index(m),0))%c + min(B.index(m),k)])
#Bは街の移動順序
#cはループの長さ

Submission status: Accepted

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

B = [0]
visited = [False] * n
for i, b in enumerate(B):
    if visited[b]:
        break
    visited[b] = True
    B.append(A[b])

j = B.index(b)
r = (k - j) % (i - j)
ans = B[j:][r] + 1 if k >= j else B[k] + 1

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
ts = [[] for _ in range(n)]

p = 0
t = 0
while True:
    ts[p].append(t)
    if t == k:
        print(p + 1)
        exit()
    if len(ts[p]) == 2:
        if (k - ts[p][0]) % (ts[p][1] - ts[p][0]) == 0:
            print(p + 1)
            exit()
    p = a[p]
    t += 1

Submission status: Accepted

Solution code:
import sys
import time

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

queue = {}

start = -1
count = 1

now_town = 1

for i in range(K):
    if town_list[now_town - 1] in queue:
        start = town_list[now_town - 1]
        break
    queue[town_list[now_town - 1]] = count
    now_town = town_list[now_town - 1]
    count += 1

if start == -1:
    print(now_town)
    sys.exit()

roop = len(queue) - (queue[start] - 1)
before_len = queue[start]

print(list(queue.keys())[(K - before_len) % roop + before_len - 1])

Submission status: Accepted

Solution code:
import sys
import numpy as np


def solve(N, K, xs):
    "void()"
    town_to_time = np.zeros(N, np.uint32)
    time_to_town = np.zeros(N, np.uint32)
    cur = 1
    for i in range(K):
        cur = xs[cur - 1]
        # print(town_to_time, time_to_town, cur)
        if town_to_time[cur - 1]:
            # visited before
            period = i + 1 - town_to_time[cur - 1]
            rest = K - i - 1
            rest %= period
            # print(rest, town_to_time[cur - 1], town_to_time[cur - 1] + rest)
            print(time_to_town[town_to_time[cur - 1] + rest - 1])
            return

        town_to_time[cur - 1] = i + 1
        time_to_town[i] = cur
    print(cur)


IN1 = """
4 5
3 2 4 1
"""

IN2 = """
6 727202214173249351
6 5 2 5 3 2
"""

IN3 = """
6 100
2 3 4 5 6 1
"""


def main():
    """
    >>> as_input(IN1)
    >>> main()
    4
    >>> as_input(IN2)
    >>> main()
    2
    >>> as_input(IN3)
    >>> main()
    5
    """
    N, K = map(int, input().split())
    xs = np.array(list(map(int, input().split())))
    solve(N, K, xs)


def _test():
    import doctest
    as_input(IN1)
    main()
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
dp = [False]*(N+1)
tele = 0
for i in range(10**6):
    if i==0:
        tele = 1
        dp[tele]=True
    else:
        tele = A[tele]
        if dp[tele]==True:
            finish = i
            tele1 = tele
            break
        else:
            dp[tele]=True
#print(finish)
#print(tele)
tele = 0
for i in range(10**6):
    if i == 0:
        tele = 1
        if tele == tele1:
            start = i
            break
    else:
        tele = A[tele]
        if tele == tele1:
            start = i
            break
#print(start)
loop = finish-start
if K<=start:
    ans = 1
    for i in range(K):
        ans = A[ans]
    print(ans)
else:
    ans = 1
    for i in range(start+(K-start)%loop):
        ans = A[ans]
    print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
pl=list(map(int,input().split()))
cl=[0]*2*n
order=[]
next=0
for i in range(k):
  if cl[next]==0:
    cl[next]=1
    next=pl[next]-1
  elif cl[next]==1:
    cl[next]=2
    order.append(next+1)
    next=pl[next]-1
  else:
    kk=len(order)
    hasuu=cl.count(1)
    newk=k-hasuu
    ans=newk%kk
    print(order[ans])
    break
else:
  print(next+1)

Submission status: Accepted

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

stop = False
#行き止まりcheck
used = set()
current = 1
old = -1
route = []
route_b4 = []
neverloop = True
#bagunoもと
for i in range(n):
    if old == current:
        stop == True
    if current in used:
        for i,city in enumerate(route):
            if city == current:
                route = route[i:]
                neverloop = False
            route_b4.append(city)

        break
    route.append(current)
    used.add(current)
    old = current
    current = a[current]
if neverloop == True:
    route_b4 = []
if stop==True:
    if len(route_b4) + len(route) >= k:
        if len(route_b4) > k:
            #自信ない
            print(route_b4[k])
        else:
            print(route[k-len(route_b4)])
    else :
        print(route[len(route)-1])
else:
    if len(route_b4) + len(route) >= k:
        if len(route_b4) > k:
            print(route_b4[k])
        else:
            print(route[k-len(route_b4)])
    else:
        total = k + len(route_b4)
        print(route[(k-len(route_b4))%len(route)])

#print(stop)
#print(route_b4)
#print(route)
#巡回路チェック

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
roop_town = None
town_list = [1]
town_set = set([1])
for cur_town in town_list:
    if a_list[cur_town-1] in town_set:
        roop_town = a_list[cur_town-1]
        break
    town_list.append(a_list[cur_town-1])
    town_set.add(a_list[cur_town-1])
if roop_town == None:
    print(town_list[k])
else:
    roop_index = town_list.index(roop_town)
    roop_num = len(town_list) - roop_index
    if k<=roop_index:
        print(town_list[k])
    else:
        k_rooped_index = (k-roop_index)%roop_num
        print(town_list[roop_index+k_rooped_index])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
route = [1]
for i in range(N):
  route.append(A[route[i]-1])
prepart = route.index(route[-1])
cycle = len(route) - prepart - 1
if K > N:
  K =(K-prepart)%cycle +prepart
print(route[K])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
town=[0]
set={0}
i=0
while True:
  idx=town[-1]
  if a[idx] in set:
    s=a[idx]
    i+=1
    break
  else:
    i+=1
    town.append(a[idx])
    set.add(a[idx])
if i!=n:
  idp=town.index(s)
  chain=len(town[:idp])
  cycle=len(town[idp:])
  if k<=chain:
    print(town[k]+1)
  else:
    p=(k-chain)%cycle + chain
    print(town[p]+1)
else:
  print(town[k%n]+1)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    to = [[None]*n for _ in range(60)]
    to[0] = a[:]
    for i in range(1, 60):
        for j in range(n):
            to[i][j] = to[i-1][to[i-1][j]-1]
    p = 1
    for i in range(59, -1, -1):
        num = 1 << i
        if k >= num:
            k -= num
            p = to[i][p-1]
    print(p)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
pl=list(map(int,input().split()))
cl=[0]*2*n
res=[]
next=0
for x in range(k):
  if cl[next]==0:
    cl[next]=1
    next=pl[next]-1
  elif cl[next]==1:
    res.append(next+1)
    cl[next]+=1
    next=pl[next]-1
  else:
    lroop=len(res)
    k-=cl.count(1)
    num=k%lroop
    print(res[num])
    break
else:
  print(next+1)

Submission status: Accepted

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


def main():
    [n, k] = [int(e) for e in si().split()]
    trace = dict()
    for i in range(1, n+1):
        trace[i] = 0

    l = [int(e) for e in si().split()]
    i, cnt = 1, 0
    while k > 0:
        k -= 1
        cnt += 1
        i = l[i-1]
        if i == 1 or trace[i] != 0:
            cy = cnt-trace[i]
            k %= cy
            break
        trace[i] = cnt
    while k > 0:
        i = l[i-1]
        k -= 1
    print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

d = li.index(num)
ans = (k-d)%(len(li)-d)+d

print(li[ans])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
Nlist = {}
Alist = {}
visit = {}
count = 1
for a in input().split():
    a = int(a)
    Alist[count] = a
    count = count+1

count = 1
visit[0] = 1
Nlist[1]=0
while True:
    if Alist[visit[count-1]] in Nlist:
        memo = Alist[visit[count-1]]
        break
    visit[count] = Alist[visit[count-1]]
    Nlist[visit[count]] = count
    count = count+1

if K < count:
    print(visit[K])
else:

    loop = count-Nlist[memo]
    K = K-(count-loop)
    K = K % loop
    K = K+Nlist[memo]
    print(visit[K])

Submission status: Accepted

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

dist = [-1 for i in range(n)]
dist[0] = 0

now_town = 0
freq = 0
for i in range(k):
    next_town = a[now_town] - 1
    if dist[next_town] != -1:
        freq = (i+1) - dist[next_town]
        const = dist[next_town]
        break
    dist[next_town] = i + 1
    now_town = next_town

if freq == 0:  # ループが発生していない場合
    print(next_town+1)
else:  # ループが発生している場合
    freq_ = (k - const) % freq
    if freq_ == 0:
        print(next_town+1)
    else:
        now_town = next_town
        for i in range(freq_):
            now_town = a[now_town] - 1
        print(now_town+1)

Submission status: Accepted

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

dist = [-1 for i in range(n)]
dist[0] = 0

now_town = 0
flg = 0  # ループが生じているかを判定するフラグ
for i in range(k):
    # print(i)
    next_town = a[now_town] - 1
    if dist[next_town] != -1:
        flg = 1
        diff = (i+1) - dist[next_town]
        const = dist[next_town]
        break
    dist[next_town] = i + 1
    now_town = next_town

# print(dist)
# print("diff", diff)
# print("const", const)

if flg == 0:
    print(next_town+1)
elif flg == 1:
    c = (k - const) % diff
    # print("c =", c)
    # print("next_town = ", next_town)
    if c == 0:
        print(next_town+1)
    else:
        now_town = next_town
        # print(now_town)
        for i in range(c):
            next_town = a[now_town] - 1
            now_town = next_town
            # print(now_town)
        print(now_town+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
N, K = map(int, input().split())
A = [int(i) - 1 for i in input().split()]

s = set()
s.add(0)
cur = 0
num = 0
d = defaultdict(int)
d[0] = 0
ls = [0]
for i in range(K):
    if A[cur] not in s:
        cur = A[cur]
        num += 1
        d[cur] = i+1
        ls.append(cur)
        s.add(cur)
    else:
        cur = A[cur]
        num += 1
        edges_heiro = num - d[cur]
        nokori = K - num
        print(ls[d[cur] + nokori%edges_heiro] + 1)
        sys.exit()
print(cur + 1)

Submission status: Accepted

Solution code:
import sys
import time
st = time.perf_counter()
def inpl():
    return list(map(int, input().split()))
# ------------------------------

N, K = map(int, input().split())
A = list(map(lambda a: int(a)-1, input().split()))
T = [A]

for i in range(59):
    prev = T[-1]
    T.append([prev[a] for a in prev])

now = 0
for k,v in enumerate(T):
    if ((1<<k)&K)>0:
        now = v[now]
print(now+1)


# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda a: int(a) - 1, input().split()))
 
T = [A]
for _ in range(59):
    prev = T[-1]
    T.append([prev[a] for a in prev])
 
now = 0
for d, P in enumerate(T):
    if ((1 << d) & K) > 0:
        now = P[now]
print(now + 1)

Submission status: Accepted

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

alr=[False]*n
alr[0]=True
now_in=0

if k<=2*(10**5)+1:
    for i in range(k):
        now_in=a[now_in]-1
    print(now_in+1)
    sys.exit()

#ループのスタートを見つける
for i in range(n+1):
    now_in=a[now_in]-1
    if alr[now_in] is False:
        alr[now_in]=True
    else:
        start=now_in
        break

count_r=0
now_in=start
for i in range(2*(10**5)+1):
    now_in=a[now_in]-1
    count_r+=1
    if now_in==start:
        break

now_in=0
count=0
while now_in!=start:
    now_in=a[now_in]-1
    count+=1

c=k-count
plus=c%count_r
for i in range(plus):
    now_in=a[now_in]-1

print(now_in+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
was = []
tf = [False] * N
place = 1
cnt = 0

while tf[place-1] == False:
  if cnt < K:
    tf[place-1] = True
    was.append(place)
    place = A[place-1]
    cnt += 1
  else:
    print(place)
    break;
else:
  loop = cnt - was.index(place)
  num = (K-cnt) % loop + was.index(place)
  print(was[num])

Submission status: Accepted

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

town = 0
cnt = 0

visited = [False] * n
visited[0] = -1

start_cnt = 0
for i in range(n*2):
    town = A[town]
    if visited[town] != False:
        start_cnt = i + 1
        loop = i - visited[town]
        break
    else:
        visited[town] = i

town = 0

if k >= start_cnt:
    k = (k-start_cnt)%loop+start_cnt

for i in range(k):
    town = A[town]

print(town+1)

Submission status: Accepted

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

town = 0
cnt = 0

# memo = []
# visited = [False] * n
# visited[0] = -1

# start = 0
# loop = 10**8
# start_cnt = 0
# for i in range(n*2):
#     town = A[town]
#     memo.append(town)
#     if visited[town] != False:
#         start_cnt = i + 1
#         loop = i - visited[town]
#         break
#     else:
#         visited[town] = i
#
# for i in range((k-start_cnt)%loop):
#     town = A[town]
#
# print(town+1)

visited = [False] * n
visited[0] = 0

for i in range(n):
    town = A[town]
    if visited[town]:
        good_town = town
        break
    visited[town] = i+1

town = good_town

for i in range(n):
    town = A[town]
    if town == good_town:
        loop = i + 1

if k >= visited[good_town]:
    k = ((k-visited[good_town])%loop)+visited[good_town]


town = 0
for i in range(k):
    town = A[town]
print(town+1)

Submission status: Accepted

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

visited = [-1]*(n+1)
pos = 1
visited[pos] = 0
loop = 0
root=[1]
for i in range(1,n+1):
  pos = a[pos-1]
  if visited[pos] == -1:
    visited[pos] = i
    root.append(pos)
  else:
    loop = i - visited[pos]
    mae = visited[pos]
    break
if k < mae:
  print(root[k])
else:
  index=(k-mae)%loop
  print(root[index+mae])

Submission status: Accepted

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

N,K = map(int,readline().split())
A = [0] + list(map(int,readline().split()))

pos = 1

while K:
  if K & 1:
    pos = A[pos]
  A = [A[A[i]] for i in range(N + 1)]
  K >>= 1
  
print(pos)

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

t = [[-1] * N for _ in range(61)]
t[0] = [A[i] - 1 for i in range(N)]
for k in range(1, 61):
    for i in range(N):
        t[k][i] = t[k - 1][t[k - 1][i]]

u = 0
for k in range(61):
    if K >> k & 1:
        u = t[k][u]

print(u + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
c = 1
for i in range(n):
    ans.append(a[ans[i] - 1])
b = ans.index(ans[n])
if k < b:
    for p in range(k):
        c = a[c - 1]
else:
    for p in range((k-b) % (n-b)+b):
        c = a[c - 1]
print(c)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(lambda x: x-1, map(int, input().split())))
isVisit = [False]*n
visits = []
visit = 0
for i in range(n):
    if isVisit[visit]:
        break
    else:
        isVisit[visit] = True
        visits.append(visit)
        visit = A[visit]

if len(visits)>k:
    print(visits[k]+1)
else:
    k -= visits.index(visit)
    visits = visits[visits.index(visit):]
    print(visits[k%len(visits)]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
tmp = [0 for _ in range(N)]
# bagに入る要素が多すぎてエラーが出ている

spot = 1
road = [1]
tmp[0] = 1
for _ in range(K):
    n_s = A[spot-1]
    if not tmp[n_s-1] == 1:
        road.append(n_s)
        tmp[n_s-1] = 1
        spot = n_s
    else:
        spot = n_s
        break

till_loop = road.index(spot)
# print(till_loop)
loop = road[till_loop:]
# print(loop)
cycle_len = len(road) - road.index(spot)
# print(cycle_len)
answer = loop[(K-till_loop) % cycle_len]

print(answer)