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:
def solve(n,k,A):
    if A[0]==0:
        return 0
    visited=set()
    visited.add(0)
    C=[0]
    p=A[0]
    while p not in visited:
        visited.add(p)
        C.append(p)
        p=A[p]
    l=len(C)
    s=C.index(p)
    if k<=s:
        return C[k]
    cycle=l-s
    k-=s
    r=k%cycle
    return C[s+r]

def main():
    n,k=map(int,input().split())
    A=tuple(map(lambda x: int(x)-1,input().split()))
    ans=solve(n,k,A)+1
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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


def main():
    n, k = map(int, input().split())
    a_list = [0] + list(map(int, input().split()))

    prevs = {}
    c = 0
    pos = 1
    while c < k and pos not in prevs:
        prevs[pos] = c
        pos = a_list[pos]
        c += 1

    if c >= k:
        print(pos)
    else:
        loop_count = c - prevs[pos]
        c_base = prevs[pos]
        kmod = (k - c_base) % loop_count
        prev_poss = list(prevs.keys())[c_base:]
        print(prev_poss[kmod])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

visited = [False] * N
loop = [0]
cur_town = 0
step = 0
while True:
    if visited[cur_town]:
        loop = loop[loop.index(cur_town):-1]
        step -= len(loop)
        print(loop[(K - step) % len(loop)] + 1)
        exit()
    else:
        visited[cur_town] = True
        cur_town = A[cur_town] - 1
        loop.append(cur_town)
        step += 1
        if step == K:
            print(cur_town + 1)
            exit()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

loop = [0]
town = 0
visited = defaultdict(lambda: None)
visited[town] = 0

period = 0
for i in range(1, k+1):
    town = a[town]
    if visited[town] != None:
        offset = visited[town]
        period = i - offset 
        break
    else:
        loop.append(town)
        visited[town] = i

if period == 0:
    print(town+1)
else:
    print(loop[offset+((k-offset)%period)]+1)

Submission status: Accepted

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

if K < N:
    for i in range(K):
        now = A[now]
    print(now)
else:
    visited = [0 for i in range(N+1)]
    for i in range(1, N+2):
        if visited[now] == 0:
            visited[now] = i
            now = A[now]
        else:
            T = i-visited[now]
            tmp = visited[now] + (K-i+1)%T
            print(visited.index(tmp))
            break

Submission status: Accepted

Solution code:
def binarySearch (arr, l, r, x): 
  
    # Check base case 
    if r >= l: 
  
        mid = l + (r - l) // 2
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return mid 
          
        # If element is smaller than mid, then it  
        # can only be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present  
        # in right subarray 
        else: 
            return binarySearch(arr, mid + 1, r, x) 
  
    else: 
        # Element is not present in the array 
        return -1
n,k=map(int,input().split( ))
s=input().split( )
p=[]
g=0
while binarySearch(p,0,len(p)-1,int(g))==-1:
    p.append(int(g))
    g=int(s[int(g)])-1
x=p.index(g)
y=len(p)
if k>=y:
    k+=1
    u=p[x:y]
    k-=x
    v=(k)%(y-x)
    print(u[v-1]+1)
else:
    print(p[k]+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
flag = True
went = {1}
go = [1]
i = 0
while flag:
  if a[i] not in went:
    go.append(a[i])
    went.add(a[i])
    i = a[i]-1
  else:
    flag = False
loop = go[go.index(a[i]):]
if len(go) > k:
  print(go[k])
else:
  k -= len(go)-len(loop)
  ans = k % len(loop)
  print(loop[ans])

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
i=0
x=0
plot=[0]
while i<n:
    x=lis[x]-1
    i+=1
    plot.append(x)
#print(plot)
y=plot[-1]
for i in range(n):
    j=n-i-1
    if y==plot[j]:
        t=i+1
        break
#print(t)
for i in range(n):
    if plot[i]==plot[i+t]:
        am=i
        break
#print(am)
if k<=am:
    print(plot[k]+1)
else:
    print(plot[am+(k-am)%t]+1)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq

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

#c=[list(map(int,input().split())) for _ in range(n)]
#c.sort(key=lambda x:x[0])
#dp=[]
def rec(arr,c,now,cnt,stop=False ,s_val=0):
    if stop and s_val==cnt:
        return now,cnt
    if c[now]:
        return now,cnt
    c[now]=True
    return rec(arr,c,a[now],cnt+1,stop=stop,s_val=s_val)
    

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

#n=2*10**5
#a=[i for i in range(2*10**5+1)]


c=[False for _ in range(n+1)]
start,s_to_rep_num=rec(a,c,1,0)
c=[False for _ in range(n+1)]
end,rep_n=rec(a,c,start,0)
val=k
s=1
#print(s_to_rep_num,rep_n)
if s_to_rep_num<k:
    s=start
    val=(k-s_to_rep_num)%rep_n
c=[False for _ in range(n+1)]
ans,cnt=rec(a,c,s,0,stop=True,s_val=val)
print(ans)

Submission status: Accepted

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,k = mp()
a = lmp()
a.insert(0,0)
here = 1
cnt = 0
hajimete = [0]*(n+1)
hajimete[0] = -1
used = set()
used.add(1)
flag = False
for i in range(k):
    cnt += 1
    here = a[here]
    if here not in used:
        used.add(here)
        hajimete[here] = cnt
    else:
        flag = True
        break
if not flag:
    print(here)
else:
    loop = cnt - hajimete[here]
    town = hajimete[here] + ((k-hajimete[here]) % loop)
    print(hajimete.index(town))

Submission status: Accepted

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

ar = [-1 for i in range(n+1)]
ar[1] == 0
ni = 1
t = 0
while k > t:
    t += 1
    if t == k:
        print(a[ni-1])
        exit()
    elif ar[a[ni-1]] > -1:
        break
    else:
        ar[a[ni-1]] = t
        ni = a[ni-1]

mod = t-ar[a[ni-1]]
idx = ar[a[ni-1]]+((k-ar[a[ni-1]])%mod)
print(ar.index(idx))

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
path = {i:A[i]-1 for i in range(N)}
flags = [-1] * N
before = 0
flags[0] = 0
for i in range(N):
  after = path[before]
  if flags[after] > -1:
    loop = i - flags[after] + 1
    first = flags[after]
    break
  before = after
  flags[after] = i+1

if first < K:
  print(flags.index(first + (K-first) % loop) + 1)
else:
  print(flags.index(K) + 1)

Submission status: Accepted

Solution code:
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
Q = deque()
Q.append(0)

Seen = [-1] * N
Seen[0] = 0
loop = 0
point = 0
while True:
    now = Q.popleft()
    nex = A[now]
    nex -= 1
    if Seen[nex] == -1:
        Seen[nex] = Seen[now] + 1
        Q.append(nex)
    elif Seen[nex] != -1:
        first = Seen[nex]
        loop = Seen[now] - Seen[nex] + 1
        point = nex
        break

if first > K:
    ind = Seen.index(K)
    print(ind+1)
    exit()

p = (K - first) % loop
Q.clear()
Q.append(point)
ans = point
while p > 0:
    no = Q.popleft()
    ans = A[no]
    ans -= 1
    Q.append(ans)
    p -= 1
print(ans + 1)

Submission status: Accepted

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

visited = [-1] * n
cnt = 0
n = 0
while True:
    visited[n] = cnt
    nx = As[n] - 1
    cnt += 1
    # ループ入った場合
    if visited[nx] != -1:
        first = visited[nx]
        if k <= first:
            for i,v in enumerate(visited):
                if v == k:
                    print(i+1)
                    exit()    
        a = (k-first)%(cnt-first)
        loop = [v-first for v in visited]
        for i,x in enumerate(loop): 
            if x == a:
                print(i+1)
                exit()
        break
    n = nx

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
p = 1
i = 0
while True:
    p = a[p - 1]
    if b[p - 1] > 0 or p == 1:
        break
    else:
        i += 1
        b[p - 1] = i
bp = b[p - 1]
if k <= bp:
    print(b.index(k) + 1)
else:
    l = bp + (k - bp) % (i + 1 - bp)
    print(b.index(l) + 1)

Submission status: Accepted

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

history = {}
cycle = []
pos = 1
isEnd = False
for i in range(2*N):
    if pos in history:
        for j in range(len(cycle)):
            if cycle[j] == pos:
                head = cycle[:j]
                cycle = cycle[j:]
                isEnd = True
                break

    if isEnd:
        break

    history[pos] = 1
    cycle.append(pos)
    pos = As[pos-1]


#print(cycle)

if K < len(head):
    print(head[K])
else:
    mod = (K-len(head)) % len(cycle)
    print(cycle[mod])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dfs(num,lis,count,target):
    visited[num]=count
    n_city=A[num]
    if visited[n_city]!=-1:
        lis.append(num)
        if target<=count:
              print(lis[target]+1)
        else:
            rep=len(lis)-visited[n_city]
            target-=visited[n_city]
            amari=target%rep
            temp=lis[visited[n_city]:]
            print(temp[amari]+1)
        exit()
    else:
        lis.append(num)
        dfs(n_city,lis,count+1,target)
    

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

visited=[-1]*N

dfs(0,[],0,K)

Submission status: Accepted

Solution code:
def d_teleporter():
    N, K = [int(i) for i in input().split()]
    A = [int(i) - 1 for i in input().split()]  # 0-origin

    from collections import defaultdict
    visit = [0]
    visit_dict = defaultdict(list)
    visit_dict[0] = [0]
    current = 0
    is_found_first = False
    for i in range(N):
        current = A[current]
        if len(visit_dict[current]) == 1 and not is_found_first:
            count_to_loop = visit_dict[current][0]
            loop_length = i - visit_dict[current][0] + 1
            is_found_first = True
        visit.append(current)
        visit_dict[current].append(i + 1)

    if K <= N:
        return visit[K] + 1
    net_moving_time = ((K - count_to_loop) % loop_length) + count_to_loop
    # 上の visit に必要な分だけ付け足してもいいが，実行時間は変わらなかった
    current = 0
    for _ in range(net_moving_time):
        current = A[current]
    return current + 1

print(d_teleporter())

Submission status: Accepted

Solution code:
import numpy as np
n,m=list(map(int,input().split()))
a=np.array(list(map(int,input().split())))
b=np.zeros(n)

mod = 2*n

tmp = 0
for i in range(mod):
  if b[tmp] == 2:
    break
  b[tmp] += 1
  tmp = a[tmp] -1
  
s = len(a[b==1])
t = len(a[b==2])

if m > s:
  m = (m-s)%t + s
tmp = 0
for i in range(m):
  tmp = a[tmp] -1
  
print(tmp+1)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(200000)
    input = sys.stdin.readline

    #まずは、どこで閉路が発生しているかを見極める。また、このときに、閉路の辺の数を求める。
    #次に、町1から閉路の始点となっている街にたどり着くまでの辺の数を求めて、Kから引く。これをGとする。
    #Gを閉路の辺の数で割ったあまりを求める。

    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    #path[n] -> 街nに最初につくまでに移動した回数
    path = {}
    #count は現在の移動回数を保持しておく変数
    info = []
    def dfs(n,count):
        if n in path:
            #閉路が発生している、ということなので、path[n]が閉路の始点にたどり着くまでに必要な移動回数
            # count - path[n] +1 が閉路を構成している辺の数
            info.append(path[n])
            info.append(count - path[n] +1)
        else:
            count += 1
            path[n] = count
            nx = A[n-1]
            dfs(nx,count)
    dfs(1,-1)
    x,y = info
    if K <= x:
        for k,v in path.items():
            if v == K:
                print(k)
    else:
        K -= x
        K %= y
        for k,v in path.items():
            if v-x == K:
                print(k)


main()

Submission status: Accepted

Solution code:
n ,k =map(int,input().split())
a = list(map(int,input().split()))
p = {i for i in range(n)}
now = 1
ok = [0 for i in range(n)]
cou = 1
ok[0] = 1
while True:
    cou += 1
    nex = a[now-1]
    if ok[nex-1] == 0:
        ok[nex-1] = cou
    elif ok[nex-1] != 0:
        break
    now = nex
    if cou == k+1:
        print(nex)
        exit()

lost = k - (ok[nex-1]-1)
lokz = cou - ok[nex-1]

p = lost%lokz
ans = ok.index(ok[nex-1]+p)+1
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ns = list(map(int, input().split()))
l = [1]
seen = set()
cur = 1
flag = True
while flag:
    i = ns[cur-1]
    cur = i
    if i in seen:
        ri = l.index(i)
        roop = l[ri:]
        flag = False
    else:
        l.append(i)
        seen.add(i)
if k <= len(l)-1:
    print(l[k])
else:
    print(roop[(k-len(l))%len(roop)])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [0] + A
# Dに何回目の移動で到達したか記録してみるか
D = [[] for _ in range(N+1)]

def judge(idx, now):
    cnt = 1
    n = A[now]
    while n != now:
        n = A[n]
        cnt += 1
    t = K - idx - 1
    t %= cnt
    return t

now = 1
i = 0
j = True
while i < K:
    now = A[now]
    D[now].append(i)
    if j and len(D[now]) > 2:
        i = K - judge(i, now) - 1
        j = False
    i += 1
   
print(now)

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
from bisect import bisect_left, bisect_right, insort
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def MS(): return map(str,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
#N = I()
#A = [LI() for _ in range(N)]

n,k = MI()
a = LI()
ans = [1] * n
memo = [-1] * n
memo[0] = 0
s = 0
for i in range(1,n):
    if memo[a[ans[i-1]-1]-1] == -1:
        ans[i] = a[ans[i-1]-1]
        s += 1
        memo[ans[i] - 1] = s

    else:
        t = memo[a[ans[i-1]-1]-1]
        break
if k <= t:
    print(ans[k])
elif t == 0:
    print(ans[(k - 1) % (s-t +1) +1])
else:
    print(ans[(k-(t-1)-1) % (s-t+1) + t])

Submission status: Accepted

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

jumps = 0
point = 1
arrived = [False] * (N + 1)
history = [0] * (N * 2)
arrived[1] = True
history[0] = 1
warped = False

while jumps < K:
    next_point = A[point]
    if not warped and arrived[next_point]:
        last_jump = 0
        while history[last_jump] != next_point:
            last_jump += 1
        loop_num = jumps - last_jump + 1
        jumps += ((K - jumps) // loop_num - 1) * loop_num
        warped = True

    arrived[point] = True
    if jumps < N * 2:
        history[jumps] = point
    point = next_point
    jumps += 1

print(point)

Submission status: Accepted

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

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

    data = []
    visited = set()
    data.append(1)
    visited.add(1)
    ai = 1
    while True:
        ai = A[ai - 1]
        if ai in visited:
            break
        data.append(ai)
        visited.add(ai)
    d_index = data.index(ai)
    if K > d_index:
        rep_data = data[d_index:]
        rep_len = len(rep_data)
        K -= d_index
        print(rep_data[K - K // rep_len * rep_len])
    else:
        print(data[K])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=[0]+a
vis={}
cnt=0
cur=1
total=0
while True:
    if cur in vis:
        break
    vis[cur]=True
    cur=a[cur]
    total += 1
vis = {}
cycle=0
while True:
    if cur in vis:
        break
    vis[cur]=True
    cur=a[cur]
    cycle += 1
if k>total:
    k -= (total-cycle)
    k=k%cycle
    while k>0:
        cur=a[cur]
        k -= 1
    print(cur
    )
else:
    cur=1
    while k>0:
        cur=a[cur]
        k -= 1
    print(cur)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
li = list(map(int, input().split()))
li_a = []
for i in li:
    i -=1
    li_a.append(i)
k = li_a[0]
dic = {}
for i in range(N):
    dic[i] = [False, 0]
dic[0] = [True, 0]
loop = 0
for i in range(1, N+1):
    if dic[k][0] == True:
        loop = i - dic[k][1]
        start = dic[k][1]
        start_k = k
        break
    dic[k] = [True, i]
    k = li_a[k]
    
if K-start <= 0:
    ans = 0
    for i in range(K):
        ans = li_a[ans]
    print(ans+1)
    sys.exit()

amari = (K-start)%loop
if amari == 0:
    print(start_k+1)
else:
    ans = start_k
    for i in range(amari):
        ans = li_a[ans]
    print(ans+1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = [0] + list(map(int, readline().split()))
    visit = [0]*(N+1)
    nx = 1
    count = 0
    while True:
        now = nx
        nx = A[now]
        count += 1
        if visit[nx] == 0:
            if count == K:
                print(nx)
                break
            else:
                visit[nx] = count
                continue
        else:
            move = (K - visit[nx]) % (count - visit[nx])
            city = visit.index(visit[nx] + move)
            print(city)
            break






if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

is_first_visit = [True for i in range(N)]

now_city = 1
visited_history = []
num_to_visit = K

is_finished = False

while is_first_visit[now_city-1]:
    is_first_visit[now_city-1] = False
    visited_history.append(now_city)
    now_city = A[now_city-1]
    num_to_visit -= 1
    
    if num_to_visit == 0:
        is_finished = True
        break

if is_finished:
    print(now_city)
else:
    loop_route = visited_history[visited_history.index(now_city):]
    loop_length = len(loop_route)

    print(loop_route[loop_route.index(now_city) + (num_to_visit % loop_length)])

Submission status: Accepted

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

visited = [None] * N
visited[0] = 0
period = None
k = K
cur = 0
while 0 < k:
    next_town = A[cur]
    k -= 1
    if visited[next_town] is None or period is not None:
        visited[next_town] = visited[cur] + 1
    else:
        period = visited[cur] + 1 - visited[next_town]
        k -= k // period * period
    cur = next_town
print(cur + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=tuple(map(int,input().split()))
b=[-1 for i in range(n)]
b[0]+=1
h=0
for i in range(0,k):
    h=a[h]-1
    
    if b[h]==-1:
        b[h]=i+1
    
    else:
        t=i+1-b[h]
        for j in range((k-i-1)%t):
            h=a[h]-1
        print(h+1)
        break
else:
    print(h+1)

Submission status: Accepted

Solution code:
n,k=list(map(int,input().split()))
As=list(map(int,input().split()))
root=[1]
count=[0]*n
count[0]+=1

cnt=0
for _ in range(k):
    dis=As[root[-1]-1]-1
    if count[dis]!=0:
        cnt+=1
        break
    else:
        root.append(dis+1)
        count[dis]+=1
if cnt==1:
    first=root.index(As[root[-1]-1])
    print(root[(k-first)%(len(root)-first)+first])
else:
    print(root[-1])

Submission status: Accepted

Solution code:
inputs = input().split(' ')
town_cnt = int(inputs[0])
trans_cnt = int(inputs[1])

towns = input().split(' ')
towns = [int(x) - 1 for x in towns]

king = 0
loop_dic = {}
loop_diff = 0
loop_cyc = 0
is_loop = False
for i in range(trans_cnt):
    if loop_dic.get(king) is None:
        loop_dic[king] = i
        king = towns[king]
    else:
        loop_diff = loop_dic.get(king)
        loop_cyc = i - loop_dic.get(king)
        is_loop = True
        break

if is_loop:
    trans_cnt = ((trans_cnt - loop_diff) % loop_cyc) + loop_diff
    king = 0
    for i in range(trans_cnt):
        king = towns[king]

print(king + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
towns=[-1]*n
towns[0]=0
current=1
for i in range(1,n+2):
  current=a[current-1]
  if i==k+1:
    loop=k+2
    thing=0
    place=1
    break
  elif towns[current-1]==-1:
    towns[current-1]=i
  else:
    loop=i-towns[current-1]
    thing=towns[current-1]
    place=current
    break
k-=thing
b=k%loop
current=place
for i in range(b):
  current=a[current-1]
  if towns[current-1]==-1:
    towns[current-1]=i
print(current)

Submission status: Accepted

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
L = []
S = set()
i = 1
cnt = 0
while (not i in S) and cnt != K:
    S.add(i)
    L.append(i)
    cnt += 1
    i = A[i]

if cnt == K:
    print(i)
else:
    j = L.index(i)
    ans = L[(j + (K - j) % (cnt - j)) % cnt]
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int], nb: int) -> int:
    seen = {}
    cur = 0
    move = 0
    while move < nb and cur not in seen:
        seen[cur] = move
        move += 1
        cur = values[cur] - 1
    if move == nb:
        return cur + 1
    cycle_length = move - seen[cur]
    _nb_cycles, rest = divmod(nb - move, cycle_length)
    LOG.debug((cur, cycle_length, move, seen))
    for _ in range(rest):
        cur = values[cur] - 1
    return cur + 1


def do_job():
    "Do the work"
    LOG.debug("Start working")
    N, K = map(int, input().split())
    values = list(map(int, input().split()))
    assert len(values) == N
    result = solve(values, K)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

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

def main():
    N, K = map(int, readline().rstrip().split())
    A = list(map(int, readline().rstrip().split()))
    d = {i+1: a for i, a in enumerate(A)}
    if K <= N:
        pre = 1
        for _ in range(K):
            pre = d[pre]
        print(pre)
        return

    pre = 1
    visited = set([1])
    visited_l = [1]
    for i in range(N):
        pre = d[pre]
        if pre in visited:
            break
        visited.add(pre)
        visited_l.append(pre)
    
    loop_start = visited_l.index(pre)
    loop = i - loop_start + 1

    num_loop = (K - loop_start) // loop
    now = loop_start + num_loop * loop
    for i in range(now+1, K+1):
        pre = d[pre]
    
    print(pre)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

visi_point = collections.defaultdict(list)

posi = 1
for i in range(K):
    next_posi = A[posi]
    if len(visi_point[next_posi]) >= 2:
        break
    visi_point[next_posi].append(i+1)
    posi = next_posi
# print(visi_point)

for k, v in visi_point.items():
    if K in v:
        print(k)
        break
    if len(v) >= 2:
        if (K - v[0]) % (v[1] - v[0]) == 0:
            print(k)
            break

Submission status: Accepted

Solution code:
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

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

def read_s_list_loop(n):
    return [input() for _ in range(n)]

N,K = read_int_map()
An = read_int_list()
memo = [0]*(N+1)
memo_indx = [0]*(N+1)
memo[1] = 1
memo_indx[1] = 0
seq_an = [1]
next_place = An[0]
for i in range(len(An)):
    if memo[next_place] == 0:
        seq_an.append(next_place)
        memo[next_place] = 1
        memo_indx[next_place] = i + 1
        next_place = An[next_place-1]
    else:
        break
loop_idx = memo_indx[next_place]
loop_list = seq_an[loop_idx:]
if K <= len(seq_an)-1:
    print(seq_an[K])
else:
    num = (K - len(seq_an)) % len(loop_list)
    print(loop_list[num])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
machi_dict = {}
while True:
    if next_machi in machi_dict:
        break
    count += 1
    machi_dict[next_machi] = 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1

z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)

Submission status: Accepted

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

p = 0

if K > N:
    city = [-1]*N
    city[0] = 1
    while city[A[p]-1] == -1:
        city[A[p]-1] = city[p]+1
        p = A[p]-1
    K = (K-city[p]) % (city[p]-city[A[p]-1]+1)
    p = A[p]-1

for i in range(K):
    p = A[p]-1

print(p+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
b = [0]*(n+1)
cnt = 0
temp = 1
rep = 0
while 1:
    cnt += 1
    if b[temp] == 0:
        b[temp] = cnt
    else:
        rep = cnt-b[temp]
        # print(rep,cnt-1,b[temp])
        # print(b)
        break
    temp = a[temp]
# print((k-b[temp]+1) % rep)
if (k-b[temp]+1) >= 0:
    for i in range((k-b[temp]+1) % rep):
        temp = a[temp]
    print(temp)
    exit()
else:
    temp = 1
    for i in range(k):
        temp = a[temp]
    print(temp)

Submission status: Accepted

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

B = [1] + [A[1]]
S = set(B)
i = 1
while i+1 == len(S):
    B.append(A[B[i]])
    S.add(A[B[i]])
    i += 1

for i in range(len(B)-1):
    if B[i] == B[-1]:
        a = i
        break

if K <= a:
    print(B[K])
else:
    print(B[a+ ((K-a) % (len(B)-a-1))])

Submission status: Accepted

Solution code:
n, k, *a = map(int, open(0).read().split())
now = 0
st = set()
ls = []
while not now in st:
    st.add(now)
    ls.append(now)
    now = a[now]-1
bi = ls.index(now)
lp = len(ls) - bi
if k<=bi: print(ls[k]+1)
else:
    k -= bi
    k %= lp
    print(ls[bi+k]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
# 1から
rec=[-1]*(n+1)
rec[1]=0
now=1
wp=0
flag=False
while k>wp:
    rec[now]=wp
    nx=a[now]
    rest=k-wp
    loop=rec[now]-rec[nx]+1
    if rest<loop:
        flag=True

    if rec[nx]==-1 or flag:
        wp+=1
        now=nx
    else:
        rest%=loop
        wp=k-rest
        flag=True
print(now)