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())
S = list(num-1 for num in map(int, input().split()))
loc = 0

arrived = [0]*N
ar = set()
cnt = 0
while not loc in ar:
    arrived[cnt] = loc
    ar.add(loc)
    loc = S[loc]
    cnt += 1

if K < cnt:
    print(arrived[K]+1)
else:
    for i in range(cnt):
        if arrived[i] == loc:
            K -= i
            roop = cnt-i
            K %= roop
            print(arrived[i+K]+1)
            break

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, K = map(int, readline().split())
A = list(map(lambda x: x - 1, map(int, readline().split())))
visited = [False for i in range(N)]

cur = 0
cycle = []
start = 0
while True:
    if visited[cur]:
        start = cur + 1
        break

    visited[cur] = True
    cycle.append(cur + 1)
    cur = A[cur]

# print(cycle)
cycle_start_idx = 0
for i in range(len(cycle)):
    if cycle[i] == start:
        cycle_start_idx = i
        break

if K <= cycle_start_idx:
    print(cycle[K])
    exit()


cycle_len = len(cycle) - cycle_start_idx
idx = (K - cycle_start_idx) % cycle_len
print(cycle[idx + cycle_start_idx])

Submission status: Accepted

Solution code:
def main():
    n, k = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    R = [1]
    RS = set(R)
    cnt = 0
    while True:
        nx = A[R[-1] - 1]
        if nx in RS:
            st = R.index(nx)
            R = R[st:]
            break

        R.append(nx)
        RS.add(nx)

        cnt += 1
        if cnt == k:
            print(nx)
            exit()

    m = (k - cnt) % len(R)
    print(R[m - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
A = [0] + [int(i) for i in input().split()]
# first study the cycle of A
cycle = [A[1]]
i = A[1]
visited = set(cycle)
while A[i] not in visited:
    cycle.append(A[i])
    visited.add(A[i])
    i = A[i]
interest_ind = cycle.index(A[i])
second_part = cycle[interest_ind:]
p = len(cycle) - interest_ind
k -= 1
if k < interest_ind:
    print(cycle[k])
else:
    k -= interest_ind
    k %= p
    print(cycle[interest_ind + k])

Submission status: Accepted

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

from pprint import pprint
import sys
sys.setrecursionlimit(10 ** 6)

n_towns, k_times = map(int, input().split())
teleport = list(map(int, input().split()))

seq = []
flags = [False] * n_towns
visited = [0] * n_towns

flags[0] = True
seq.append(0)
visited[0] += 1

town_prev = 0

while True:
    town_next = teleport[town_prev] - 1
    visited[town_next] += 1
    if flags[town_next]:
        seq.append(town_next)
        break
    seq.append(town_next)
    flags[town_next] = True
    town_prev = town_next

loop_len = 0
for town, count in enumerate(visited):
    if count == 2:
        loop_idx = seq.index(town)
# print(loop_idx)

# print(f'seq: {seq}')

if k_times < loop_idx:
    print(seq[k_times] + 1)
else:
    arr = seq[loop_idx:len(seq) - 1]
    r = (k_times - loop_idx) % len(arr)
    print(arr[r] + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,0)
loop=[]
keys = [i for i in range(1,n+1)]
values=[0 for i in range(n)]
dd=dict(zip(keys, values))
start=10
nex=1
pos=a
while start!=nex:
  start=1
  if dd[nex]==1:
    pos=loop.index(nex)
    loop1=loop[pos:]
    nex=1
  else:
    loop.append(nex)
    dd[nex]=1
    nex=a[nex]

if pos==a:
  length=len(loop)
  print(loop[k%length])
else:
  length=len(loop1)
  if k>=len(loop):
    k=k-pos
    print(loop1[k%length])
  else:
    print(loop[k])

Submission status: Accepted

Solution code:
from collections import deque
n, k = list(map(int, input().split()))
a = [0, ] + list(map(int, input().split()))
stack = deque([1, ])
visited = [0] * (n + 1)
hist = []
open = []
loop = []
while stack:
    now = stack.popleft()
    if visited[now] == 1:
        b = hist.index(now)
        open = hist[:b]
        loop = hist[b:]
        break
    next = a[now]
    visited[now] = 1
    hist.append(now)
    stack.append(next)
if k < len(open):
    print(open[k])
else:
    print(loop[(k - len(open)) % len(loop)])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

    town = defaultdict(int)
    cn = defaultdict(int)
    
    visited = set()
    visited.add(0)
    cnt = 0
    tmp = A[0]-1
    town[cnt] = 0
    ii = 0
    
    while True:
        if(tmp not in visited):
            visited.add(tmp)
            cnt += 1
            cn[tmp] = cnt
            town[cnt] = tmp
            tmp = A[tmp]-1
        else:
            ii = cn[tmp]
            break
    
    if(K >= len(town)):
        if(ii != 0):
            K -= ii
            ans = town[(K%(len(town)-ii))+ii]+1
        else:    
            ans = town[K%(len(town))]+1
        print(ans)
    else:
        ans = town[K]+1
        print(ans)
main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
# せいぜいO(|A|)回=O(10^5)のジャンプでループするよね．
# ループしたかどうかの判定（いままで訪れたノードを再び訪れたかの判定はset,dictを使えば高速なはず）

# とりあえずKとか関係なくループするまでの数を調べる
visited = {}  # 訪れたノードの番号-1と訪れたときを保存しているノード
visited[0] = 0 # 初期化
next_node = A[0]-1
count=1
while True:
    if next_node in visited:
        loop_node = next_node
        break
    visited[next_node]=count
    count+=1
    next_node = A[next_node] - 1

loop_width = count-visited[loop_node]
first_loop = visited[loop_node]

if K<=first_loop:
    now_node = 0
    for _ in range(K):
        now_node = A[now_node] -1
    print(now_node + 1)
    exit()
rest = (K-first_loop)%loop_width
now_node=loop_node
for _ in range(rest):
    now_node = A[now_node] - 1
print(now_node + 1)

Submission status: Accepted

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

used = set()
history = []

cur = 0
used.add(0)

while True:
    history.append(cur)
    next_cur = A[cur] - 1
    if next_cur in used:
        loop_start = history.index(next_cur)
        break
    used.add(next_cur)
    cur = next_cur

B = history[loop_start:]
if K <= loop_start:
    result = history[K]
else:
    result = B[(K-loop_start) % len(B)]

print(result+1)

Submission status: Accepted

Solution code:
#from collections import defaultdict, deque
#import itertools
#import numpy as np

def main():
    N, K = tuple(int(c) for c in input().split(' '))
    A = [None] + list(int(c) for c in input().split(' '))
    
    memo = {1: 0}
    machi = 1
    k = 0
    while k < K:
        machi = A[machi]
        k += 1
        if not machi in memo:
            memo[machi] = k
        else:
            cycle = k - memo[machi]
            res = (K-k) % cycle
            k = K - res
            #print(machi, K, k, cycle, res)

    print(machi)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

r = []
u = [False for _ in range(n)]
def dfs(x):
  if u[x]:
    return x
  else:
    u[x] = True
    r.append(x)
    return dfs(a[x]-1)

b = dfs(0)
for i in range(len(r)):
  if b == r[i]:
    break
#print(b,i,r)
if k >= i:
  print(r[i+(k-i)%(len(r)-i)]+1)
else:
  print(r[k]+1)

Submission status: Accepted

Solution code:

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

loop = []
trace = [0] * (N+1)
visited = set()

ai = 1
for i in range(N+1):
    if ai in visited:
        ind = trace.index(ai)
        loop = trace[ind:i]
        trace = trace[:ind]
        break
    visited.add(ai)
    
    trace[i] = ai # ??
    ai = A_list[ai-1]


if len(trace) > K:
    print(trace[K])
else:
    ind = K - len(trace)
    ind = ind % len(loop)
    print(loop[ind])

Submission status: Accepted

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    #
    n, k = map(int, input().strip().split())  # """ 街数n, 移動回数k """
    a = list(map(lambda x: int(x) - 1, input().strip().split()))  # """ 転送先 : 街i から街a[i]"""

    #
    eprint("a", end=':\n')
    eprint(a)
    #
    path = []
    visitedlist = [False for _ in range(n)]
    pos = 0
    cnt=0   # 現在位置posに来るまでの，「移動回数」

    while True:
        if cnt==k:
            print(pos+1)
            return
        if visitedlist[pos]:
            start = pos
            break
        cnt+=1
        path.append(pos)
        visitedlist[pos] = True
        pos = a[pos]

    eprint('path ', end=':\n')
    eprint(path)

    for i in range(len(path)):
        if path[i] == start:
            cycle = path[i:]

    eprint('cycle ',end=':\n')
    eprint(cycle)

    m=len(cycle)
    cnt1=k-cnt
    cnt2=cnt1%m
    print(cycle[cnt2]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

i = 0
j = 0
while g[j] == -1:
    if i == k:
        print(j + 1)
        exit()
    g[j] = i
    i += 1
    j = a[j]

for i in range((k - g[j]) % (i - g[j])):
    j = a[j]
print(j + 1)

Submission status: Accepted

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

next=0
hoge=[]
zisyo={}

for i in range(n):
    next=A[next]
    if next in zisyo:
        t=next
        break
    else:
        zisyo[next]=1
        hoge.append(next)
hoge_1=[]
hoge_2=[]
for i in range(len(hoge)):
    if hoge[i]==t:
        hoge_1=hoge[:i]
        hoge_2=hoge[i:]

ans=0
if k<=len(hoge_1):
    for i in range(k):
        ans=A[ans]
else:
    k=k-len(hoge_1)-1
    k=k%len(hoge_2)
    ans=hoge_2[0]
    for i in range(k):
        ans=A[ans]


print(ans+1)

Submission status: Accepted

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

pos = 0
memo = [[False, 0] for _ in range(N)] # memo[i]: [bool, tel_cnt] , [数えたか、何回移動したか]
memo[0] = [True, 0]
distance = 0
l_pos = 0
tel_cnt = 0
while True:
    next = A[pos]
    tel_cnt += 1
    if memo[next][0]: # 数えた
        r_pos, l_pos = memo[pos][1], memo[next][1]
        distance = r_pos - l_pos
        break
    memo[next][1] = tel_cnt
    memo[next][0] = True
    # index 更新
    pos = next

def find_idx_by_telcnt(tel_cnt):
    for i in range(N):
        m = memo[i]
        if m[1] == tel_cnt:
            return i

if K <= l_pos:
    print(find_idx_by_telcnt(K) + 1)
else:
    diff = K - l_pos
    rem = diff % (distance + 1)
    ans_pos = l_pos + rem
    print(find_idx_by_telcnt(ans_pos) + 1)

Submission status: Accepted

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

N, K = map(int, input().split())
As = list(map(int, input().split()))
Ms = dict()

cnt = 0
pos = 0
Ms[pos] = cnt

found = False

while cnt < K:
    pos = As[pos]-1
    cnt += 1
    if (not found) and (pos in Ms.keys()):
        found = True
        K = (K - Ms[pos]) % (cnt - Ms[pos]) + cnt
    Ms[pos] = cnt

print(pos+1)

Submission status: Accepted

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

l = [0]*n
s = set()
x = 0

for i in range(n):
    machi = a[x]
    if machi in s:
        hajime = l.index(machi)
        repeat = l[hajime:i]
        break
    x = machi-1
    l[i] = machi
    s.add(machi)
else:
    amari = k%n
    print(l[amari-1])
    exit()

if k < hajime:
    print(l[k-1])
else:
    amari = (k-hajime)%len(repeat)
    print(repeat[amari-1])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
t = [0]*(n+1)
l = [1]
t[1] = 1
x = 1
y = 0
for i in range(n):
    if(t[a[x]] == 0):
        x = a[x]
        t[x] = 1
        l.append(x)
    else:
        z = i+1
        y = l.index(a[x])
        break
if(k>y):
    print(l[(k-y)%(z-y)+y])
else:
    print(l[k])

Submission status: Accepted

Solution code:
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
seen = []
seen_sort = [1]
start = 1

while True:
    tmp = a[start - 1]
    seen.append(start)
    index = bisect.bisect_left(seen_sort, tmp)
    if index >= len(seen_sort) or seen_sort[index] != tmp:
        seen_sort.insert(index, tmp)
    else:
        repeat_index = seen.index(tmp)
        repeat_len = len(seen) - repeat_index
        break
    start = tmp

if k <= repeat_index:
    print(seen[k])
else:
    print(seen[repeat_index + ((k - repeat_index) % repeat_len)])

Submission status: Accepted

Solution code:
N , K = map(int,input().split())
B = {}
C = {}
D = {0}
A = list(map(int,input().split()))
place = 0
num = 0
C[0] = 0
while True:
    place = int(A[place]) - 1
    num += 1   
    if place in D:
        Y = int(num) - int(C[place])
        break
    elif num == K:
        break
    else:
        B[num] = place
        C[place] = num
        D.add(place)
try:
    X = (K - num) % Y
    print(B[C[place] + X] + 1)
except:
    print(place+1)

Submission status: Accepted

Solution code:
n, k = map(int , input().split())
A = list(map(int, input().split()))
now = 1
point = [0 for _ in range(n)]
count = 0
step = 0
flag = True
flag2 = True
for i in range(k):
  point[now-1] += 1
  if(point[now-1] == 2):
    if(flag):
      step = 0
      init = i
      flag = False
  if(point[now-1] == 3):
    flag2 = False
    break
      
  now = A[now-1]
  step += 1;
  
  
if(flag2):
  print(now)
else:
  a = k-(init-1)
  k = a%step
  k += (init-1)
  now = 1
  for i in range(k):
    now = A[now-1]
  print(now)

Submission status: Accepted

Solution code:
from collections import deque
n,k = map(int, input().split())
a=[-1]
a.extend(list(map(int, input().split())))
route=[-1]*(n+1)
q=deque([1])
cnt=0
roop=0
while q:
  p=q.pop()
  route[p]=cnt
  if route[a[p]] == -1:
    q.append(a[p])
    cnt+=1
  else:
    roop=[route[a[p]],route[p]]
    break

if k <= min(roop):
  for i,r in enumerate(route[1:],start=1):
    if r == k:
      print(i)
else:
  t=(k-min(roop))%(max(roop)-min(roop)+1)
  for i,r in enumerate(route[1:],start=1):
    if r == t+min(roop):
      print(i)

Submission status: Accepted

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

d = []
color = [0] * n
nxt = 1
for i in range(m):
    if color[nxt-1] == 3:
        loop = len(d)
        rest = m - i
        q = rest % loop
        print(d[q])
        exit()
    elif color[nxt-1] == 2:
        d.append(nxt)
        color[nxt-1] += 1
        nxt = a[nxt-1]
    else:
        color[nxt-1] += 1
        nxt = a[nxt-1]
print(nxt)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
loop_=[1]
l_set=set()
lst=list(map(int,input().split()))

tar=None
for i in range(k):
    num=lst[loop_[-1]-1]
    if num in l_set:
        tar=num
        break
    else:
        loop_.append(num)
        l_set.add(num)

if tar==None:
    print(loop_[k])
    exit()    
loop__=loop_[loop_.index(tar):]

num=k+1-len(loop_)
try:
  print(loop__[num%len(loop__)-1])
except:
  print(1)

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
A = list(map(int, input().split()))
A = {i+1:A[i] for i in range(len(A))}

if k <= n:
    current = 1
    for i in range(k):
        current = A[current]
    print(current)
else:
    current = 1
    count = 0
    pos = []
    visited = {i+1:-1 for i in range(len(A))}
    for i in range(k):
        #print(pos, visited[current])
        if visited[current] >= 0:
            circle = pos[visited[current]:]
            ans = k - visited[current]
            ans = ans % len(circle)
            #print(visited[current], ans, circle, circle[ans])
            print(circle[ans])
#             circle_len = count - visited[current]
#             #final_pos = visited[current] + 
#             print(pos[k%circle_len])
            break
        
        pos.append(current)
        visited[current] = count
        count += 1
        current = A[current]

Submission status: Accepted

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

visited_ls = [0] * (n+1)
tour_ls = []
now = 1
times = 1
while True:
    # 現在地についての処理
    tour_ls.append(now)
    visited_ls[now] += 1

    nex = a_ls[now]
    if visited_ls[nex]:
        first_ind = tour_ls.index(nex)
        before_loop = first_ind
        loop_ls = tour_ls[first_ind:times]
        break
    # 現在地を更新
    now = nex
    times += 1
if k - before_loop >= 0:
    ind = (k - before_loop) % len(loop_ls)
    print(loop_ls[ind])
else:
    print(tour_ls[k])

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    lst = list(map(int, input().split()))
    ma = [l-1 for l in lst]
    
    visited = [False for _ in range(n)]
    history = []
    now = 0
    while True:
        if visited[now]:
            history.append(now)
            break
        
        visited[now] = True
        history.append(now)
        
        now = ma[now]
    if k <= len(history)-1:
        print(history[k] + 1)
        return
    
    last = history[-1]
    for i in range(n):
        if history[i] == last:
            roopstart = i
            break
    syokilst = history[:roopstart]
    rooplst = history[roopstart:-1]
    syokilen = len(syokilst)
    rooplen = len(rooplst)
    resi = k - syokilen
    mod = resi%(rooplen)
    print(rooplst[mod] + 1)
main()

Submission status: Accepted

Solution code:
n , k = map(int,input().split())
S = list(map(int,input().split()))
l = [1]
for i in range(2*n):
    l.append(S[l[i]-1])

L = len(l)
def f(s, e):
    a = s
    b = s

    while True:
        a += 2
        b += 1
        if a >= e:
            return None
        if l[a] == l[b]:
            break

    a = 0
    while True:
        a += 1
        b += 1
        if b >= e:
            return None
        if l[a] == l[b]:
            break

    return a, b

c, d = f(0, L)
loop = l[c:d]

m = d - c 
A = c + 1
B = d + 1
if k <=  n:
    print(l[k])
else:
   K = (k - c) % m
   print(loop[K])

Submission status: Accepted

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

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

visited = [0] * N

order = []

cur = 1
cnt = 0

while True:
    if visited[cur-1] == 0:
        visited[cur-1] += 1
        if cnt == K:
            print(cur)
            break

    elif visited[cur-1] == 1: # cur == 2
        
        order_from_cur = order[order.index(cur):]
        r = (K-cnt) % len(order_from_cur)

        final = order_from_cur[r]
        print(final)
        break
    order.append(cur)
    cur = A[cur - 1]
    cnt += 1

Submission status: Accepted

Solution code:
import numpy as np

n, k = list(map(lambda x: int(x), input().split(' ')))
teles = list(map(lambda x: int(x)-1, input().split(' ')))

beforeloop = 0
loop = []

done = False

ni, nj = 0, 0
pi, pj = 0, 0
while True:
  pi = teles[pi]
  pj = teles[teles[pj]]
  ni += 1
  nj += 2
  # ni回, piにて確実にループ内
  # ループ一周は nj - ni(= ni)要素&回
  if ni == k:
    print(pi+1)
    done = True
    break
  if pi == pj:
    beforeloop = ni
    break
    
if not done:
  current = pi
  loop.append(current)
  while True:
    current = teles[current]
    if current == pi:
      break
    loop.append(current)
  print(loop[(k - beforeloop) % len(loop)]+1)

Submission status: Accepted

Solution code:
n,k =map(int,input().split())
a=list(map(int,input().split()))
a = [1] + a
def next(i):
    return a[i]

z = [0] * (n+1)

place = 1
T = 0
interval = 0
if k < n:
    for i in range(k):
        place = next(place)
    print(place);exit()
place = 0
k += 1
for i in range(n):
    place = next(place)
    if z[place] != 0:
        interval = T - z[place]  + 1
        break
    z[1] = 1 
    T += 1
    z[place] = T

m = (k-z[place])%interval
for i in range(m):
    place = next(place)
print(place)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
town = [0] * n
move = []
next1 = a[0] - 1
flag = 0
for i in range(k):
    town[next1] += 1
    move += [next1]
    if town[next1] > 1:
        flag = 1
        break
    if i == k-1:
        break
    next1 = a[next1] - 1
if flag == 0:
    print(next1+1)
else:
    first = move.index(move[-1])
    roop = move[first:-1]
    print(roop[(k - first)%len(roop)-1]+1)

Submission status: Accepted

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

loop_count = 0
loop = [0] * N
i = 1
town = A[0] - 1
loop[0] = i
if N > K:
    for _ in range(K - 1):
        town = A[town] - 1
    print(town + 1)
else:
    while True:
        if loop[town] == 0:
            i += 1
            loop[town] = i
            town = A[town] - 1
        else:
            break
    loop_size = i - loop[town] + 1
    
    if loop_size != 0:
        K = (K - i) % loop_size
    
    for _ in range(K):
        town = A[town] - 1
    
    print(town + 1)

Submission status: Accepted

Solution code:
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

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

A = [A[i]-1 for i in range(len(A))]

mem = [0]*N
mem2 = [0]*N

idx = 0
count1 = 0
while True:
    mem[idx] += 1
    if mem[idx] == 2:
        break
    count1 += 1
    idx = A[idx]


idx2 = idx
count2 = 0

count2 += 1
idx2 = A[idx2]

while True:
    if idx2 == idx:
        break
    count2 += 1
    idx2 = A[idx2]

tmp = count1 - count2

if tmp >= K:
    ans = 0
    for _ in range(K):
        ans = A[ans]
else:
    e = (K - tmp) % count2 + tmp
    ans = 0
    for _ in range(e):
        ans = A[ans]

print(ans+1)

Submission status: Accepted

Solution code:
N , K  = map ( int  ,input().strip().split(" ") ) 
list0 = list( map ( int  , input().strip().split(" ") ) ) ;

set1  = set([0]) ; 
list1 = [0] ;

for x in range ( N ) :
	p = list0[list1[-1]] -1 ;
	if p in  set1 : 
		break ;
	set1.add ( p )  ;
	list1.append( p ) ;

if K < len( list1 ) :
	print ( list1[K] +1 ) ;
else :
	c0 = list1.index( p ) ;
	K -= c0 ;
	c = K % ( len(list1) - c0 ) ;
	print ( list1[c0 + c] + 1) ;

Submission status: Accepted

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

ptr = 0
cnt = 0
visited = [-1 for i in range(N)]
visited[0] = 0
for i in range(N):
  nxt = A[ptr]
  if visited[nxt] != -1:
    break
  else:
    cnt += 1
    ptr = nxt
    visited[nxt] = cnt
visited = [(i,v) for i,v in enumerate(visited) if v!=-1]
visited = [i for i,v in sorted(visited,key=lambda x:x[1])]
idx = visited.index(nxt)
loop = len(visited)-idx
calc = K if K < len(visited) else (idx + (K-idx)%loop )
print(visited[calc]+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
dic={}
for a,b in enumerate(A):
  dic[b]=a
B=[-1]*len(A) # A[i] on cnt
cnt=0
i=0 # current town
flg=0
while True:
  if B[i] == -1:#first time
    B[i]=cnt
  elif flg == 0:#loop
    delta=cnt-B[i]
    nokori=(K-cnt) % delta # after loop
    if nokori == 0:
      break
    flg = 1
    cnt = K - nokori
    #print('loop',delta,nokori,cnt)
  i=A[i]-1
  cnt+=1
  
  #print(cnt,i,A[i])
  if cnt == K:
    break

print(i+1)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools



sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N, K = map(int,input().split())
A = [int(i) for i in input().split()]
Temp = [0]*N
imp = [0]*3
ans = [0]

def rec(next, kore):
    #print(kore)
    #print(next)
    if(kore==K):
        ans[0] = next
        return
    if(Temp[next-1] == 0):
        Temp[next-1] = kore
        rec(A[next-1], kore+1)
    else:
        imp[0] = kore-Temp[next-1]
        imp[1] = kore
        imp[2] = next
    return
#Temp[0] = 1
rec(A[0],1)
#print(imp)
#print("fin")
for i in range(N):
    Temp[i] = 0

if(ans[0] != 0):
    print(ans[0])
else:
    K -= imp[1]
    K = K%imp[0]
    #print(K)
    if(K==0):
        print(imp[2])
    else:
        #print("a", K)
        rec(A[imp[2]-1], 1)
        print(ans[0])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
i_to_a = {i+1: int(a) for i, a in enumerate(input().split())}

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

next_v = 1
loop_start_index = 0
while True:    
    if seen_d[next_v]:
        break
    seen_d[next_v] = 1
    seen.append(next_v)
    next_v = i_to_a[next_v]
loop_start_index = seen.index(next_v)
to_loop = seen[:loop_start_index]
additional = seen[:loop_start_index]
loop = seen[loop_start_index:]

additional_l = len(additional)
loop_l = len(loop)

if k > additional_l:
    s = (k - additional_l) % loop_l
    print(seen[additional_l + s])
else:    
    print(seen[k])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

d = dict()
seen = set()
i = 0
cur = 0
while True:
    if i > 0:
        cur = A[cur] - 1
    if cur in seen:
        break
    d[i] = cur
    seen.add(cur)
    i += 1

def get_loop_size(start):
    c = start
    size = 0
    while size == 0 or c != start:
        c = A[c] - 1
        size += 1
    return size

for k, v in d.items():
    if v == cur:
        start = k
        break
loop_size = get_loop_size(d[start])
if K < start:
    print(d[K] + 1)
else:
    idx = start + (K - start) % loop_size
    print(d[idx] + 1)

Submission status: Accepted

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

freq=[]
for i in range(n+1):
	freq.append(0)

pos=1
pos=a[pos]
cycle=[]
while freq[pos]==0:
	freq[pos]+=1
	cycle.append(pos)
	pos=a[pos]

flag=0
c1=[]
c2=[]
for i in range(len(cycle)):
	if cycle[i]==pos:
		flag=1
	if flag==0:
		c1.append(cycle[i])
	else:
		c2.append(cycle[i])

#print(c1,c2)

l1=len(c1)
l2=len(c2)

if k<=l1:
	print(c1[k-1])
else:
	k-=l1
	print(c2[k%l2-1])

Submission status: Accepted

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

visit_time = [None] * N
now = 0
visit_time[now] = 0
loop_start_city = None
loop_last_city = None
loop_first = None
loop_second = None
for i in range(1, 2 * 10 ** 5 + 1):
    last = now
    now = A[now]-1
    if visit_time[now] is not None:
        loop_start_city = now
        loop_last_city = last
        loop_first = visit_time[now]
        loop_second = i
        break
    else:
        visit_time[now] = i
if loop_start_city is not None and K > loop_first:
    K += 1
    K -= loop_first
    K %= (loop_second - loop_first)
    now = last
else:
    now = 0
for i in range(K):
    now = A[now]-1
print(now+1)

Submission status: Accepted

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

first = {}
first[1] = 0
second = {}
flag = 1
i = 0
warp = 0
while flag:
    warp += 1
    if A[i] in first.keys():
        second[A[i]] = warp
        flag = 0
        break
    first[A[i]] = warp
    i = A[i] - 1

loop_town = []
stand = 0
loop = 0
small = 0
for key, value in second.items():
    stand = first[key]
    if K < value:
        small = 1
    loop = value - first[key]
    for key2, value2 in first.items():
        if first[key] <= value2 < value:
            loop_town.append(key2) 

if small == 0:
    print(loop_town[(K-stand)%loop])
else:
    keys = [k for k, v in first.items() if v == K]
    print(keys[0])

Submission status: Accepted

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

log=[0 for i in range(N+1)]
log[1]=1
re=0
p=1
while True:
    p=A[p]
    log[p]+=1
    re+=1
    if log[p]==2:
        break

if K<re:
    p=1
    for i in range(K):
        p=A[p]
    print(p)
    
else:
    K=K-re
    log=[0 for i in range(N+1)]
    log[p]=1
    re=0
    while True:
        p=A[p]
        log[p]+=1
        re+=1
        if log[p]==2:
            break

    K=K%re
    for i in range(K):
        p=A[p]
    print(p)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    visited_set = set()
    visited_list = []
    now_town = 1
    while now_town not in visited_set:
        visited_list.append(now_town)
        visited_set.add(now_town)
        now_town = A_list[now_town-1]
    remainder = visited_list.index(now_town)
    period = len(visited_list) - remainder
    answer = None
    if K <= remainder:
        answer = visited_list[K]
    else:
        answer = visited_list[(K-remainder)%period + remainder]
    print(answer)

if __name__ == "__main__":
    main()