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

now=1
flg = 0
path = [1]
pathcheck ={1}
for i in range(k):
    now = a[now-1]
    if now in pathcheck:
        flg = -1
        path.append(now)
        break
    path.append(now)
    pathcheck.add(now)


if flg == 0:
    print(now)
    exit()

x1 = path.index(now)
x2 = len(path)-1
x3 = (k-x1)%(x2-x1)
print(path[x1+x3])

Submission status: Accepted

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

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

did = set()
route = [1]

now = 1
for i in range(k):
    now = d[now]
    route.append(now)
    if now in did:
        break
    did.add(now)

if k < 10 ** 6:#計算量的に間に合うので愚直に
    now = 1
    for i in range(k):
        now = d[now]

    print(now)

else:
    for i in range(len(route)):
        if route[i] == route[-1]:#routeには第二ループの始めがギリ入っている
            roop = route[i:-1]
            print(roop[(k - i) % len(roop)])#k-iは残り移動階数
            exit()

Submission status: Accepted

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

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

did = set()
route = [1]

now = 1
for i in range(k):
    now = d[now]
    route.append(now)
    if now in did:
        break
    did.add(now)

if k < 10 ** 6:
    now = 1
    for i in range(k):
        now = d[now]

    print(now)

else:
    for i in range(len(route)):
        if route[i] == route[-1]:
            roop = route[i:-1]
            print(roop[(k - i) % len(roop)])
            exit()

Submission status: Accepted

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

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

did = set()
route = [1]

now = 1
for i in range(k):
    now = d[now]
    route.append(now)
    if now in did:
        break
    did.add(now)

if k < 10 ** 6:
    now = 1
    for i in range(k):
        now = d[now]

    print(now)

else:
    for i in range(len(route)):
        if route[i] == route[-1]:
            roop = route[i:-1]
            break

    print(roop[(k - i) % len(roop)])

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:
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    tel = [0] + il()

    # 初期位置
    position = 1

    # 移動回数がN回(町の数)以下の場合
    if K <= N:
        for k in range(K):
            position = tel[position]
        print(position)
        exit()

    # 移動回数がN回(町の数)以上の場合
    for n in range(N):
        position = tel[position]

    # 既にN回移動済みのため、
    # 必要な移動回数(K)から減算
    K -= N
    # ループまでに必要な移動回数を探索
    base = position
    cnt = 1
    while base != tel[position]:
        position = tel[position]
        cnt += 1

    # Kからループ数の余りを求め、
    # 余りの回数だけ移動を行う
    for k in range(K % cnt + 1):
        position = tel[position]
    print(position)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

before = 1
start = 0
end = 0

if K <= N:
    for i in range(K):
        before = a[before]
    print(before)

# 周期がどこからどこまでかっていうのを求めると逆に時間がかかってしまうので、N回移動したあとの街っていうのをマークしたほうがはやい
    
else:
    market_town = 0
    for i in range(N):
        before = a[before]
    marked_town = before
    K -= N
    counter = 1
    while marked_town != a[before]:
        before = a[before]
        counter += 1
    K = K % counter
    for i in range(K+1):
        before = a[before]
    print(before)

Submission status: Accepted

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

def compute(city, K):
    for i in range(K):
        # 3-1番目=2
        city = As[city-1]
    print(city)

cities_visited = [False] * N
i = 0
city = 1
city_visited_time = {}
# city_visited_timeの出力結果例2
# リストの05142の順番
# {0: 0, 5: 1, 1: 2, 4: 3, 2: 4}
# ループの計算
# 最初1-1のリスト0の　3 6からスタート
while not cities_visited[city - 1]:
    cities_visited[city - 1] = True
    city_visited_time[city-1] = i
    # 次の街はリストasリスト[6-1]の5=2から
    city = As[city-1]
    i += 1
    # cityの出力結果3,4,1 6,2,5,3,2渦巻型
    # iの出力結果合計3回　5回 
loop_start = city_visited_time[city-1]
# loop_startの出力結果0 2
loop_end = i
# 出力結果i同様3 5

div = (K - loop_start) // (loop_end - loop_start)
# div出力結果242400738057749783
if K - loop_start < 0 or div == 0:
    compute(1, K)
else:
    compute(city, K - loop_start - div * (loop_end - loop_start))

Submission status: Accepted

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

b=[1]
Flag=True
now=1
arrived=set(b)
memo=1
while Flag:
    b.append(a[now-1])
    if a[now-1] in arrived:
        Flag=False
        memo=a[now-1]
    arrived.add(a[now-1])
    now=a[now-1]

loop=len(b)-b.index(memo)-1

first=b.index(memo)


if k>first:
    p,q=divmod(k-first,loop)
    print(b[first+q])
else:
    print(b[k])

Submission status: Accepted

Solution code:
# youtubeの解説で紹介されていたダブリングを使って実装してみる
import math

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

# aのindexと街番号をあわせる
a.insert(0,0)

# ダブリングのテーブル作成
db = [a]
logk = math.ceil(math.log(k, 2)) # 底を2にする。底のデフォルトがeになっているため
#print(logk)

for i in range(1, logk+1):
  d = [0] * (n+1)
  prev = db[i-1]
  for j in range(1, n+1):
    d[j] = prev[prev[j]]
  db.append(d)
#print(bin(k))
#print(len(bin(k)))
#print(db)

v = 1
for i in range(logk, -1, -1):
  bit = 1 << i
  if k & bit:
    v = db[i][v]
print(v)

Submission status: Accepted

Solution code:
import glob
import os

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    alph = []

    def rec(self, result, now, max, N):

        if now == N:
            res = ""
            for i in result:
                res += self.alph[i]
            print(res)
            return

        if now == 0:
            result[0] = 0
            self.rec(result, now+1, 0, N)
            return

        for i in range(0, max+2):
            if i == N:
                return
            result[now] = i
            if i > max:
                self.rec(result, now+1, i, N)
            else:
                self.rec(result, now+1, max, N)

    def resolve(self):

        N, K = map(int, self.input_data().split())
        A = list(map(int, self.input_data().split()))
        A.insert(0, 0)
        town_visit_time = [-1]*(N+1)

        num_loop = 0
        loop_start_count = 0
        loop_start_town = 0

        next_town = 1
        for i in range(0,N+1):
            if town_visit_time[next_town] != -1:
                num_loop = i - town_visit_time[next_town]
                loop_start_count = town_visit_time[next_town]
                loop_start_town = next_town
                break

            town_visit_time[next_town] = i
            next_town = A[next_town]

            if i+1 == K:
                print(str(next_town))
                exit(0)

        remain = (K - loop_start_count) % num_loop

        result =  loop_start_town
        for i in range(remain):
            result = A[result]

        print(str(result))

solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Accepted

Solution code:
from collections import deque

N,K=map(int,input().split())
A=list(map(int,input().split()))
if A[0]==1:
    print(1)
    exit()
if K==1:
    print(A[0])
    exit()
for i in range(N):
    A[i]-=1


#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [0]*N
L = deque()
S[0]=1
L.append(1)
count=1
pos=A[0]

for i in range(N+1):
    
    if S[pos]==0:
        count+=1
        S[pos]=count
        L.append(pos+1)
        pos=A[pos]
        
    else:
        roopcount=count-S[pos]+1
        L.append(pos+1)
        break


if count>K:
    ans=L[K]

else:
    K=K-(count-roopcount)
    K=K%roopcount
    for i in range(count-roopcount):
        ret=L.popleft()
    ans=L[K]
    
print(ans)

Submission status: Accepted

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

v = 1
s = [-1] * (n+1)
d = []
l = 0
c = 0

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

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

Submission status: Accepted

Solution code:
import sys
def f(A,N):
    INF=10**18+1
    C=[0 for _ in [0]*N]
    C[0],cp=1,0
    for i in range(2,N+2):
        if C[A[cp]]>0:return (A[cp],C[A[cp]]-1,i-C[A[cp]])
        else:C[A[cp]],cp=i,A[cp]
    return (-1,0,INF)
def main():
    N,K=tuple(map(int,sys.stdin.readline().split()))
    A=list(map(lambda x:int(x)-1,sys.stdin.readline().split()))
    a,n,m=f(A,N)
    (cp,X)=(0,K) if a==-1 or K<=n else (a,(K-n)%m)
    for _ in range(X):cp=A[cp]
    print(cp+1)
if __name__=='__main__':main()

Submission status: Accepted

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

A = [1] + [int(n) for n in input().split()]

dest = []

current = 0
count = 0
next_dest = A[current]
seen = {}

while not next_dest in seen:
    current = next_dest
    next_dest = A[current]
    dest.append(current)
    seen[current] = count
    count += 1

cycle_start = seen[next_dest]
cycle_length = seen[current] - cycle_start + 1

if K <= cycle_start:
    print(dest[K])
else:
    print(dest[cycle_start + ((K - cycle_start) % cycle_length)])

Submission status: Accepted

Solution code:
N, K = [int(i) for i in input().split(' ')]
A = [0]
A.extend([int(a) for a in input().split(' ')])
check_list = [0] * (N + 1)

town = 1
check_point = 0
initial = -1
interval = -1

for k in range(K):
    if check_list[town] > 0:
        check_point = town
        initial = check_list[town]
        interval = k - initial
        break
    check_list[town] = k
    town = A[town]

if interval == -1:
    print(town)
    exit(0)

remain = K - k

rem = remain % interval

check_list_ = list(map(lambda x: x - initial, check_list))

for i, c in enumerate(check_list_):
    if c == rem:
        print(i)
        exit(0)

Submission status: Accepted

Solution code:
from collections import Counter

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

counter = Counter()

i = 1
while True:
    if counter[i] >= 2:
        break
    counter[i] += 1
    i = A[i - 1]

loop = len([0 for v in counter.values() if v == 2])
to_loop = len([0 for v in counter.values() if v == 1])

if K > to_loop:
    K = to_loop + (K - to_loop) % loop

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

print(i)

Submission status: Accepted

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

slow = 1
fast = 1
counter = 0
for _ in range(K):
    slow = A[slow - 1]
    fast = A[A[fast-1]-1]
    counter += 1
    if slow == fast:
        break
# counter = m = lambda + k * myu
# m = lambda(開始地点) +(m - lambda)
# lambda進むとmyuの定数倍のmがlambdaから進んだ事になるのでそこがスタート地点
# get lambda
slow2 = slow
slow_start = 1
counter = 0
for _ in range(K):
    slow2 = A[slow2 - 1]
    slow_start = A[slow_start-1]
    counter += 1
    if slow2 == slow_start:
        break
lam = counter
slow3 = slow
counter = 0
for _ in range(K):
    slow3 = A[slow3 - 1]
    counter += 1
    if slow3 == slow:
        break
myu = counter

total = lam + (K-lam) % myu
length = 0
if total < K:
    length = total
else:
    length = K
current = 1
for _ in range(length):
    current = A[current-1]
print(current)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
B = [True]*N
C = [1]
now = 0
while B[now]:
    B[now] = False
    now = A[now] - 1
    C.append(now+1)
start = C.index(C[-1])
D = C[start:-1]
L = len(D)
if K < start:
    print(C[K])
else:
    K -= start
    K %= L
    print(D[K])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
teleport=list(map(int,input().split()))
double_counter=set()
# mojiretu="1"
mojiretu=["1"]
index=1
double_counter.add(index)
flag=False
for i in range(k):
    tmp=teleport[index-1]
    if tmp in double_counter:
        flag=True
        break
    else:
        double_counter.add(tmp)
        # mojiretu+=str(tmp)
        mojiretu.append(str(tmp))
        index=tmp
else:
    print(tmp)

if flag:
    # index=mojiretu.index(str(tmp))
    # roop_str=mojiretu[index:]
    # length=k%len(roop_str)-len(mojiretu[:index])%len(roop_str)
    # print(roop_str[length])

    index = mojiretu.index(str(tmp))
    roop_str=mojiretu[index:]
    length=k%len(roop_str)-len(mojiretu[:index])%len(roop_str)
    print(roop_str[length])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
teleport=list(map(int,input().split()))
double_counter=set()
# mojiretu="1"
mojiretu=["1"]
index=1
double_counter.add(index)
flag=False
for i in range(k):
    tmp=teleport[index-1]
    if tmp in double_counter:
        flag=True
        break
    else:
        double_counter.add(tmp)
        # mojiretu+=str(tmp)
        mojiretu.append(str(tmp))
        index=tmp
else:
    print(tmp)

if flag:
    # index=mojiretu.find(str(tmp))
    # roop_str=mojiretu[index:]
    # length=k%len(roop_str)-len(mojiretu[:index])%len(roop_str)
    # print(roop_str[length])

    index = mojiretu.index(str(tmp))
    roop_str=mojiretu[index:]
    length=k%len(roop_str)-len(mojiretu[:index])%len(roop_str)
    print(roop_str[length])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
teleport=list(map(int,input().split()))
double_counter=set()
# mojiretu="1"
mojiretu=["1"]
index=1
double_counter.add(index)
flag=False
for i in range(k):
    tmp=teleport[index-1]
    if tmp in double_counter:
        flag=True
        break
    else:
        double_counter.add(tmp)
        # mojiretu+=str(tmp)
        mojiretu.append(str(tmp))
        index=tmp
else:
    print(tmp)

if flag:
    # index=mojiretu.find(str(tmp))
    # roop_str=mojiretu[index:]
    # length=k%len(roop_str)-len(mojiretu[:index])%len(roop_str)
    # print(roop_str[length])

    Li = mojiretu.index(str(tmp))
    Ri = len(mojiretu)
    idx = Li + (k - Li) % (Ri - Li)
    print(mojiretu[idx])

Submission status: Accepted

Solution code:
[n, k], [*a] = [[*map(int, t.split())] for t in open(0)]
count = 0
visited = dict()
tmp = 1
while count < k:
    visited[tmp] = count
    count += 1
    tmp = a[tmp - 1]
    if tmp in visited:
        k = (k - count) % (count - visited[tmp])
        visited = {tmp: 0}
        count = 0
print(tmp)

Submission status: Accepted

Solution code:
[n, k], [*a] = [[*map(int, t.split())] for t in open(0)]
count = 0
visited = dict()
tmp = 1
while count < k:
    visited[tmp] = count
    count += 1
    tmp = a[tmp - 1]
    if tmp in visited:
        break
if count < k:
    k = (k - count) % (count - visited[tmp])
    for _ in range(k):
        tmp = a[tmp - 1]
print(tmp)

Submission status: Accepted

Solution code:
n,k=map(int,input().split(" "))
a=[int(i)-1 for i in input().split(" ")]
was=[False]*n
pos=0
while k>0 and not was[pos]:
    was[pos]=True
    pos=a[pos]
    k-=1
if k>0:
    was=[False]*n
    cyc=0
    while not was[pos]:
        was[pos]=True
        pos=a[pos]
        cyc+=1
    k%=cyc
while k>0:
    pos=a[pos]
    k-=1
print(pos+1)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#初期入力
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
#あえて構造を辞書
connection ={i:0 for i in range(1,N+1)}
for i in range(1,N+1):
    connection[i] =A[i-1]
#テレポート先は1か所、N << K だからループする。戻ってくる場所を探す。
passed =[1]
passed_set =set(passed)
intersection =0
next =connection[1]
#count_intersection =[]
#count_loop =0
for i in range(1,N+1): #スタートは１
    if next not in passed_set:
        passed.append(next)
        passed_set.add(next)
        next =connection[next]
    else:
        intersection =next
        break
#1ループの移動回数
loop_s  =passed.index(intersection)
loop_f  =len(passed) 
loop_num =loop_f -loop_s

#ループ開始前後で場合分け
ans =0
if K < loop_f:
    ans =passed[K]
else:
    K2      =K -loop_s
    q,mod   =divmod(K2,loop_num)
    ans     =passed[loop_s +mod]
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = [int(v) - 1 for v in input().split()]
    path_to_idx = {}
    path = []
    current_node = 0
    while True:
        path.append(current_node)
        path_to_idx[current_node] = len(path_to_idx)
        if path_to_idx.get(a[current_node]) is not None:
            cyclic = path_to_idx[a[current_node]]
            break
        current_node = a[current_node]

    if k < len(path):
        print(path[k]+1)
    else:
        k -= cyclic
        k %= (len(path) - cyclic)
        print(path[cyclic+k]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    if a[0] == 1:
        print(1)
        exit(0)
    if a[0] == a[a[0]-1]:
        print(a[0])
        exit(0)
    pos = a[0]
    num = 1
    nums = set([1])
    while pos not in nums:
        nums.add(pos)
        num += 1
        pos = a[pos-1]
    lastnum = pos
    prefix = 0
    pos = 1
    while pos != lastnum:
        prefix += 1
        pos = a[pos-1]
    num -= prefix
    if k > prefix:
        k = (k-prefix)%num+prefix
    pos = 1
    for _ in range(k):
       pos = a[pos-1]
    print(pos)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
result=[1]
temp=1
for i in range(n):
  temp=a[temp-1]
  result.append(temp)
temp=result.index(result[len(result)-1])
c=len(result)-temp-1
if k<n:
  print(result[k])
else:
  print(result[temp+(k-temp)%c])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(a)-1 for a in input().split()]
city=0
if K<=N:
    for k in range(K):
        city=A[city]
    print(city+1)
else:
    visited=[-1]*N
    for k in range(K):
        if visited[city]!=-1:
            roop_start=visited[city]
            cycle_num=k-roop_start
            break
        visited[city]=k
        city=A[city]
    K=(K-roop_start)%cycle_num+roop_start
    city=0
    for k in range(K):
        city=A[city]
    print(city+1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
city=1
if K<=N:
    for k in range(K):
        city=A[city]
    print(city)
else:
    visited=[-1]*(N+1)
    for k in range(K):
        if visited[city]!=-1:
            roop_start=visited[city]
            cycle_num=k-roop_start
            break
        visited[city]=k
        city=A[city]
    K=(K-roop_start)%cycle_num+roop_start
    city=1
    for k in range(K):
        city=A[city]
    print(city)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
city=0
if K<=N:
    for k in range(K):
        city=A[city]-1
    print(city+1)
else:
    visited=[-1]*N
    for k in range(K):
        if visited[city]!=-1:
            roop_start=visited[city]
            cycle_num=k-roop_start
            break
        visited[city]=k
        city=A[city]-1
    K=(K-roop_start)%cycle_num+roop_start
    city=0
    for k in range(K):
        city=A[city]-1
    print(city+1)

Submission status: Accepted

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

visited_l = [1]
visited_s = set([1])

now = 1

if k <= n:
    for i in range(k):
        now = a[now - 1]
    print(now)
else:
    for i in range(n):
        now = a[now - 1]
        if now in visited_s:
            break
        else:
            visited_l.append(now)
            visited_s.add(now)

    l = visited_l.index(now)
    loop = i - l + 1

    res = (k - len(visited_l)) % loop

    print(visited_l[l + res])

Submission status: Accepted

Solution code:

def main():
    N, K = map(int,input().split(' '))
    to = list(map(int,input().split(' ')))
    to.insert(0, 0)
    dist = [0] * (N+1) # 頭からの距離
    distance = 0
    node = 1 # start
    mod = 1
    for _ in range(N):
        node = to[node]
        K-=1
        distance += 1
        if K==0:
            print(node)
            exit(0)
        if node == 1:
            mod = distance
            break
        elif dist[node] == 0:
            dist[node] = distance
        else:
            mod = distance - dist[node]
            break
    K %= mod
    for _ in range(K):
        node = to[node]
    print(node)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#1 Doubling: O(log k)
# Python (3.8.2): TLE
# PyPy3
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n, k = 4, 5
    A = [3, 2, 4, 1]

  else:
    ##INPUT 
    #n = input()
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

  ## SUBMITION CODES HERE
  D = 60 # 10^18 is 60 digits, so we'll see to the 59th power of 2.
  MAX_N = 200005 #Namber of nodes
  to = [[0 for _ in range(MAX_N)] for _ in range(D)]

  # to[i][j]:nodes to 2^i away from j  
  for i in range(n):
    to[0][i] = A[i]
    to[0][i] -= 1

  # Doubling matrix
  for i in range(D-1):
    for j in range(n):
        to[i+1][j] = to[i][to[i][j]]

  v = 0
  for i in range(D-1, -1, -1):
    l = 1<<i # Look go to 2^i
    if l <= k:
        v = to[i][v]
        k -= l

  print(v+1)
    
main()

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
tmp = 1
First = [True]*N
First[tmp-1] = False
i = 0
mem = 0
while i < K:
    i += 1
    tmp = A[tmp-1]
    if not First[tmp-1]:
        mem = tmp
        break
    First[tmp-1] = False
count = 0
while i < K:
    i += 1
    count += 1
    tmp = A[tmp-1]
    if tmp == mem:
        break
K -= i
if K > 0:
    K %= count
for i in range(K):
    tmp = A[tmp-1]
print(tmp)

Submission status: Accepted

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n, k = 4, 5
    A = [3, 2, 4, 1]

  else:
    ##INPUT 
    #n = input()
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

  ## SUBMITION CODES HERE
  Town = []
  rec = [-1] * (n+1) # The town we haven't visited yet is -1
  idx = 1

  # Loop to the cycle
  while (rec[idx] == -1):
    rec[idx] = len(Town)
    Town.append(idx)
    idx = A[idx-1]

  # Pre-cycle
  Exce = rec[idx]
  # Intra-cycle
  Cycl = len(Town) - Exce

  if Exce > k:
    print(Town[k])
  else:
    Warp = (k - Exce) % Cycl
    print(Town[Exce+Warp])
  
main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
 
n, k = map(int, readline().split())
a = np.int32(read().split())
 
a -= 1

b = [0]
t = 0

for i in range(n):
    t = a[t]
    b.append(t)

d = b.index(b[-1]) - 1
r = len(b) - d - 2

if k > n:
    k = (k-d) % r + d

print(b[k]+1)

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(int,input().split()))
if K<=N:
    next_city=0
    for i in range(K):
        next_city=A[next_city]-1
else:
    next_city=0
    visited=[-1]*N
    visited[0]=0
    for num in range(1,N):
        next_city=A[next_city]-1
        if visited[next_city]!=-1:
            break
        visited[next_city]=num
    K=(K-num)%(num-visited[next_city])
    for i in range(K):
        next_city=A[next_city]-1
print(next_city+1)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline

N, K, *A = map(int, read().split())
A = [i - 1 for i in A]

check = [False] * N
seq = []
here = 0
while True:
    if K == 0:
        print(here + 1)
        exit()
    if check[here]:
        break
    seq.append(here)
    check[here] = True
    here = A[here]
    K -= 1

seq = seq[seq.index(here):]
circ = len(seq)
K %= circ
print(seq[K] + 1)

Submission status: Accepted

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

Submission status: Accepted

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

    next = A[present - 1]
    if visited[next - 1] != -1:
        loopLength = visited[present - 1] - visited[next - 1] + 1
        rest = (K - i) % loopLength
        if rest > 0:
            present = visited.index(visited[next - 1] + rest - 1) + 1
        break

print(present)

Submission status: Accepted

Solution code:
#ダブリング
import copy
n,k=map(int,input().split())
d=60
#d=k.bit_length()
to=[[0 for _ in range(n)] for _ in range(d)]
to[0]=[i-1 for i in map(int,input().split())]
for i in range(1,d):
  for j in range(n):
    #print(i,j,to[i])
    to[i][j]=to[i-1][to[i-1][j]]
v=0
for i in reversed(range(d)):
  l=2**i
  if l<=k:
    v=to[i][v]
    k-=l

print(v+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False]*N
# print(visited)
path = [0]
at = 0
loop = 0
visited[0]=True

for i in range(N):
    at = A[at]-1
    # print(at)
    if visited[at]:
        loop = i+1-path.index(at)
        break
    else:
        visited[at]=True
        path.append(at)
if K < len(path):
    print(path[K]+1)
else:
    print(path[(K-path.index(at))%loop+path.index(at)]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
s=[]
v=1
ord=[-1]*(n+1)
c=1
l=0
while ord[v]==-1:
  ord[v]=len(s)
  s.append(v)
  v=A[v-1]
c=len(s)-ord[v]
l=ord[v]

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

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    f = list(map(lambda x : int(x) - 1, input().split()))
    step = [-1] * n
    step[0] = 0
    now = 0
    while step[f[now]] == -1:
        step[f[now]] = step[now] + 1
        now = f[now]
        if step[now] == k:
            print(now + 1)
            return

    k -= step[now]
    loop = step[now] - step[f[now]] + 1
    k %= loop
    for _ in range(k):
        now = f[now]
    print(now + 1)
resolve()

Submission status: Accepted

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

num = list(map(int, input().split()))
t = [-1] * n
count = 0
s = 1

while t[s - 1] == -1:
  if count == k:
    break

  t[s - 1] = count
  count += 1
  s = num[s - 1]
else:
  z = (k - t[s - 1]) % (count - t[s - 1])
  s = t.index(t[s - 1] + z) + 1
print(s)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
q = list(map(int, input().split()))
v = [-1]*(n+1)
p = []
a = 1
c = 0
while 1:
    if v[a] != -1:
        l = c-v[a]
        if k < c:
            print(p[k])
        else:
            print(p[(k-v[a])%l+v[a]])
        break
    v[a] = c
    c += 1
    p.append(a)
    a = q[a-1]