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:
"""
    Satwik_Tiwari ;) .
    12th july , 2020  - Sunday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) : # Check Prime Number or not
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
def bfs(g,st,lcatable,level):
    visited = [0]*(len(g))
    visited[st] = 1
    queue = []
    queue.append(st)
    new = []
    while(len(queue) != 0):
        s = queue.pop()
        new.append(s)
        for i in g[s]:
            if(visited[i] == 0):
                level[i] = level[s]+1
                lcatable[i][0] = s
                visited[i] = 1
                queue.append(i)

    return new

def lcatable(g,n,level): #O(nlogn) make table beforehand.to answer per query in O(logn)
    mx = 0
    while(2**(mx) <=n):
        mx+=1
    # print('mx',mx)
    lcatable = [[-1]*mx for i in range(n+1)]
    bfs(g,1,lcatable,level)

    for j in range(1,mx):
        for i in range(1,n+1):
            if(lcatable[i][j-1] != -1):
                lcatable[i][j] = lcatable[lcatable[i][j-1]][j-1]

    return lcatable

def dist(x0,y0,x1,y1):
    return (abs(x0-x1) + abs(y0-y1))

def djkistra(g,st,dist): #g contains b,dist(a to b) and dist is initiaalised by 10**9 initiallly
    pq = []
    dist[st] = 0
    pq.append([0,st])
    while(len(pq) != 0):
        curr = heappop(pq)[1]
        for i in range(0,len(g[curr])):
            b = g[curr][i][0]
            w = g[curr][i][1]
            if(dist[b] > dist[curr] + w):
                dist[b] = dist[curr]+w
                pq.append([dist[b],b])
    return dist

# ini = 10**5
def solve():
    n,k = sep()
    a = lis()
    visited = [-1]*n

    curr = a[0]
    cnt = 1
    visited[0] = cnt
    cnt+=1
    ind = 0
    while(True):
        if(k==0):
            print(ind+1)
            return
        # print(curr)
        if(visited[curr-1] == -1):
            k-=1
            visited[curr-1] = cnt
            ind = curr-1
            curr = a[curr-1]
            cnt+=1

        else:
            diff = cnt - visited[curr-1]
            # print(curr,visited,cnt)
            ind = curr-1
            curr = a[curr-1]
            k-=1
            break
    # print(curr,k,diff)
    k = k%diff
    # ans = curr
    # print(k)
    while(k!=0):
        ind = curr-1
        curr = a[curr-1]
        k-=1
    print(ind+1)







testcase(1)
# testcase(int(inp()))

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, k, *a = map(int, read().split())

l = [0] * (n + 1)

q = deque([])
i = 1
while True:
    q.append(i)
    l[i] += 1
    if l[i] == 2:
        left = q.index(i)
        right = len(q)-2
        break
    i = a[i - 1]

length = right - left + 1

if k > left:
    b = k - left
    k = b % length
    print(q[left+k])
else:
    print(q[k])

Submission status: Accepted

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

visitTowns = list()
visitTimes = [0 for _ in range(N + 1)]

curTown = 1
timeBackTo = 0

curTime = 0
while True:
    if visitTimes[curTown] > 0:
        timeBackTo = visitTimes[curTown]
        break

    visitTowns.append(curTown)
    visitTimes[curTown] = curTime

    # teleport
    curTown = portals[curTown]

    curTime += 1

nonLoopCount = timeBackTo
loopSpan = len(visitTowns) - nonLoopCount

if K <= nonLoopCount:
    print(visitTowns[K])
    exit()

rem = (K - nonLoopCount) % loopSpan
print(visitTowns[nonLoopCount + rem])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
alist = list(map(int,input().split()))
memo = []
p = 1
vis = ['.']*n
while vis[p-1] == '.':
    memo.append(p)
    vis[p-1] = 'v'
    p = alist[p-1]
 
loop = memo.index(p)
if k < len(memo):
    print(memo[k])
else:
    print(memo[loop+(k-loop)%(len(memo)-loop)])

Submission status: Accepted

Solution code:
import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = np.int32(A) - 1

nxt = np.zeros((70, N), dtype=int)
nxt[0] = A
for i in range(0, 69):
    nxt[i + 1] = nxt[i, nxt[i]]

pos = 0
for i, v in enumerate(reversed(bin(K)[2:])):
    if v == '1':
        pos = nxt[i, pos]

print(pos + 1)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,K=list(map(int,input().split()))
A =[0]+list(map(int,input().split()))
town = 1
town_list = [1]
towntown = [0]*(N+1)
towntown[1]=1
count = 0
while True:
    town = A[town]
    count +=1
    if count == K:
        print(town)
        exit()
    if towntown[town] == 0:
        town_list.append(town)
        towntown[town] =1
    else:
        roop_town_num = town
        break
    
l_ini_index = town_list.index(roop_town_num)
len_roop = len(town_list)-l_ini_index 

if K <= l_ini_index:
    print(town_list[K])
else:
    print(town_list[((K-l_ini_index)%len_roop+l_ini_index)])

Submission status: Accepted

Solution code:
import sys

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    curr = 1
    left = k
    vis = {}
    while left > 0:
        curr = a[curr-1]
        left -= 1
        if not curr in vis:
            vis[curr] = k - left
        else:
            loopsize = k - left - vis[curr]
            left %= loopsize
            break
    while left > 0:
        curr = a[curr-1]
        left -= 1
    print(curr)


    return





n, k = RA()
a = RA()
solve()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
adj=[1]*n
b=[1]
now=0
while adj[now]:
  adj[now]=0
  now=a[now]-1
  b.append(now+1)
loop_start=b.index(b[-1])
loop=b[loop_start:-1]
p=len(loop)
if k<loop_start:
  print(b[k])
else:
  k-=loop_start
  k%=p
  print(loop[k])

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(lambda x: int(x)-1,input().split()))
    latest=[-1]*N
    latest[0]=0
    now=0
    while(K>0):
        K-=1
        to=A[now]
        if latest[A[now]]!=-1:
            K%=latest[now]-latest[A[now]]+1
        latest[A[now]]=latest[now]+1
        now=to
    print(now+1)
        
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

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

    B = [1]
    s = [True]*(N+1)
    s[1] = False
    nextTown = A[1]
    while s[nextTown]:
        B += nextTown,
        s[nextTown] = False
        nextTown = A[nextTown]
        
    B = np.array(B)
    loopIndex = np.where(B == nextTown)[0][0]
    loopLen = len(B) - loopIndex

    if K >= loopIndex:
        print(B[(K-loopIndex)%loopLen + loopIndex])
    else:
        print(B[K])

main()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
vis = [0]*N
p = 1
Town = []

while vis[p-1] == 0:
    Town.append(p)
    vis[p-1] = 1
    p = A[p-1]

l = Town.index(p)

if K < len(Town):
    print(Town[K])
else:
    print(Town[l + (K-l)%(len(Town[l:]))])

Submission status: Accepted

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

# 街iを訪れたらvis[i-1]を0から1にする
visited = [0] * N
# １からスタートして、訪れる街を順に記録
a = []
# １からスタート
town = 1

# 街pをまだ訪れていない場合
while visited[town - 1] == 0:
    # pを訪れたことを記録
    visited[town - 1] = 1
    # pを訪れた順番を記録
    a.append(town)
    # テレポート先はA[p-1]
    town = A[town - 1]

# ここでtownはループの先頭の町の番号
loop_head = a.index(town)

# K==len(a)-1だとちょうどaの最後で止まる
# Kがlen(a)以上だとループに入る
if K < len(a):
    print(a[K])
else:
    # ループに入る前までに移動回数をloop_head消費する
    # ループの長さはlen(a) - loop_head
    K -= loop_head
    print(a[loop_head + K % (len(a) - loop_head)])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [-1 for _ in range(N)]
visited[0] = 0
k = 0
k = A[k] - 1
count = 0
while visited[k] == -1:
  count += 1
  visited[k] = count
  k = A[k]-1
 
roop = count - visited[k] + 1
beforeroop = visited[k]
 
if K < beforeroop:
  k = 0
  for _ in range(K):
    k = A[k] - 1
  print(k+1)
else:
  K = K - beforeroop
  K = K % roop
 
  for _ in range(K):
    k = A[k]-1
  print(k+1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
alist = list(map(int,input().split()))
memo = []
p = 1
vis = ['.']*n
while vis[p-1] == '.':
    memo.append(p)
    vis[p-1] = 'v'
    p = alist[p-1]

loop = memo.index(p)
if k < len(memo):
    print(memo[k])
else:
    print(memo[loop+(k-loop)%(len(memo)-loop)])

Submission status: Accepted

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

# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n, k = input_list()
    a = input_list()
    d = {1: 0}
    pre = 1
    loop_start = 0
    loop_end = 0
    loop_pos = 0
    for i in range(1, n+1):
        new = a[pre-1]
        if d.get(new):
            loop_start = d[new]
            loop_end = i
            loop_pos = new
            break
        if i == k:
            print(new)
            exit()
        d[new] = i
        pre = new

    k -= loop_start
    k %= loop_end - loop_start
    pre = loop_pos
    for i in range(k):
        pre = a[pre-1]
    print(pre)

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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

n,k=list(map(int,input().split()))
m=list(map(int,input().split()))
a=[]
p=1
vis=[0]*n
while vis[p-1]==0:
    a.append(p)
    vis[p-1]=1
    p=m[p-1]

l=a.index(p)

if k<len(a):
    print(a[k])
else:
    k-=l
    print(a[l+k%(len(a)-l)])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    route = [0]
    visited = set([0])
    now_town = 0
    while True:
        next_town = A[now_town]
        if next_town in visited:
            break
        else:
            visited.add(next_town)
            route.append(next_town)
            now_town = next_town

    loop_start = route.index(next_town)
    loop_len = len(route[loop_start:])
    count_before_loop = len(route) - loop_len
    if K <= count_before_loop:
        ans = route[K] + 1
    else:
        K -= count_before_loop
        r = K % loop_len
        ans = route[loop_start + r] + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        self.k_max = K_max.bit_length()
        self.n = len(A)
        self.decrement = decrement
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, self.k_max):
            for j in range(self.n):
                if self.doubling[i - 1][j] != -1:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement


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


N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

Submission status: Accepted

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

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        self.k_max = K_max.bit_length()
        self.n = len(A)
        self.decrement = decrement
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, self.k_max):
            for j in range(self.n):
                if self.doubling[i - 1][j] == -1:
                    self.doubling[i][j] = -1
                else:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement


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


N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

Submission status: Accepted

Solution code:
#####################################################################################################
##### ダブリング
#####################################################################################################

"""

全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、
「K個先の要素を求めるのに O(K) かかる」ような状況において

前処理：O(N logK) 時間, O(N logK) 空間
クエリ：O(logK)

で行うことができるようにするアルゴリズム

参考
https://algo-logic.info/doubling/

ベンチマーク
https://atcoder.jp/contests/abc167/submissions/15103640


"""

import sys
input = sys.stdin.readline

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        N = len(A)
        k_max = K_max.bit_length()
        self.N = N
        self.doubling = [[-1] * N for _ in range(k_max + 1)]
        self.decrement = decrement
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, k_max):
            for j in range(N):
                if self.doubling[i - 1][j] == -1:
                    self.doubling[i][j] = -1
                else:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement


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


N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

Submission status: Accepted

Solution code:
from collections import defaultdict
n, k = map(int, input().split())
a = [0] + [int(i) for i in input().split()]
d = defaultdict(int)
next = 1
for t in range(k):
  if d[next]!=0:
    period = t - d[next]
    res = (k - t)%period
    for _ in range(res):
      next = a[next]
    break
  elif d[next]==0:
    d[next] = t
    next = a[next]
print(next)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        N = len(A)
        k_max = K_max.bit_length()
        self.N = N
        self.doubling = [[None] * N for _ in range(k_max + 1)]
        self.decrement = decrement
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, k_max):
            for j in range(N):
                if self.doubling[i - 1][j] is None:
                    self.doubling[i][j] = None
                else:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement


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


N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

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:
def main():

    n, k = (int(i) for i in input().split())
    tel = [int(i) - 1 for i in input().split()]

    # take one step with our 'slo' walker
    slo = tel[0]
    fas = tel[slo]
    k -= 1

    while k != 0 and slo != fas:
        slo = tel[slo]
        fas = tel[tel[fas]]
        k -= 1

    if k == 0:
        print(slo + 1)
        return

    cyc = 0
    while k != 0:
        slo = tel[slo]
        cyc += 1
        k -= 1
        if fas == slo:
            break

    k = k % cyc

    for i in range(k):
        slo = tel[slo]

    print(slo + 1)


main()

Submission status: Accepted

Solution code:
n,k = map(int, input().split())
a = [0] + list(map(int, input().split()))
 
now = 1
check = [-1]*(n+1)
 
for i in range(k):
  if check[now] == -1:
    check[now] = i
    now = a[now]
  else:
    loop = i - check[now]
    afterloop = (k-(i-loop))%loop
    print(check.index((i-loop) + afterloop))
    exit()
print(now)

Submission status: Accepted

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

move = 1
l = [1]
flag = [False]*(N+1)
flag[1] = True

for i in range(K):
    move = A[move-1]
    if flag[move]:
        break
    flag[move] = True
    l.append(move)

ind = l.index(move)
rest = (K-ind) % (len(l) - ind) + ind

print(l[rest])

Submission status: Accepted

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

move = 1
l = [1]
flag = [False]*(N+1)
flag[1] = True

for i in range(K):
    move = A[move-1]
    if flag[move]:
        # ind = l.index(move)
        # l = l[ind:]
        break
    flag[move] = True
    l.append(move)

# print("ind:{}".format(ind))
# print("l:{}".format(l))
ind = l.index(move)
# l = l[ind:]
rest = (K-ind) % (len(l) - ind) + ind

# print(rest)
print(l[rest])

Submission status: Accepted

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

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

visited_list = [1]
visited_set = set([1])
idx = 0


while True:
    next_idx = A_list[idx] - 1
    
    if (next_idx+1) in visited_set:
        break
    else:
        visited_list.append(next_idx+1)
        visited_set.add(next_idx+1)
        idx = next_idx

    if len(visited_list) == (K+1):
        print(visited_list[K])
        sys.exit()


cycle_start = visited_list.index(next_idx+1)  # 0-index
cycle_length = len(visited_list) - cycle_start

remain = (K - cycle_start) % cycle_length  # 0-index
idx = cycle_start + remain

print(visited_list[idx])

Submission status: Accepted

Solution code:
n, k  = map(int, input().split())
an = list(map(int, input().split()))
bn = [-1]*(n+1)

now=1
bn[1]=0
for i in range(1, k+1):
 #   print(bn)
    now = an[now-1]
    if bn[now] >0:
        rp =i-bn[now]
        p= (k-i)%rp
        for j in range(p):
            now = an[now-1]
        print(now)
        exit(0)
    bn[now]=i
print(now)

Submission status: Accepted

Solution code:
#D
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
tel = deque()
tel.append(1)
visit = [False for _ in range(n)]
visit[0] = True
for i in range(n):
    nx = a[tel[i]-1]
    if visit[nx-1] == True :
        tel.append(nx)
        #ループの始まりのindexをidxに格納
        idx = tel.index(nx)
        break
    tel.append(nx)
    visit[nx-1] = True
    
#print(tel)
#print(visit)
if k <= idx:
    goal = tel[k]
else:
    k -= idx
    loop_num = len(tel) - idx - 1
    #print('idx:',idx)
    #print('loop_num:',loop_num)
    goal = tel[idx + k%loop_num]
    
print(goal)