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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-1] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = {}
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = 1
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] >= 0:
                    # 既にループ作成済なら
                    if self.roop_dict[to] >= 0:
                        break
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = 1
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_n(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    # xからk回移動してどの場所に行けるか
    def move(self, x, k):
        if k == 1:
            return x + 1
        cnt = k
        to = x
        # ループに入る前にどのルートを通ったか
        # スタート地点から既にループに入っていた場合、headは空になる
        head = []
        # ループ脱出後どのルートを通るか
        tail = []
        # 何回ループしたか
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # まだループしておらず、踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            # ループ前なら
            if time == -1:
                head.append(to)
            # ループ後なら
            else:
                tail.append(to)
        # 例: N, K = 6 727202214173249351
        # A = [6, 5, 2, 5, 3, 2]の時
        # 1回目の移動 1 → 6
        # 2回目の移動 6 → ### ここからループが始まる ### → 2
        # ... 242400738057749783回ループ
        # 727202214173249351回目の移動 3 → 2
        # to, head, tail, time = (1, [5], [1], 242400738057749783)
        return to

N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-1] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = {}
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = 1
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] >= 0:
                    # 既にループ作成済なら
                    if self.roop_dict[to] >= 0:
                        break
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = 1
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_n(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    def move(self, x, k):
        if k == 1:
            return x + 1
        cnt = k
        to = x
        head = []
        tail = []
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # 踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)

        return to

N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)

Submission status: Accepted

Solution code:
N, K = map(int ,input().split())
A = [int(x) for x in input().split()]
checked = [False] * N
root=[0]

idx = 0
checked[0]=True

for k in range(K):
  root.append(A[idx]-1)
  idx = A[idx]-1
  if (checked[idx]):
    break
  checked[idx]=True
else:
  print(idx+1)
  exit(0)

for i, r in enumerate(root):
  if r == root[-1]:
    break

root2=root[i:]
l = len(root2)-1
idx = root2[(K-i)%(l)]
print(idx+1)

Submission status: Accepted

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

vis=[0]*(N+1)
now=1
vis[now] = 1
his=[now]
while 1:
  new = A[now-1]
  if vis[new]==0:
    vis[new]=1
    his.append(new)
    now = new
  else:
    idx = his.index(new)
    cycle = his[idx:]
    margin = his[:idx]
    break
    
if K <= len(margin):
  print(his[K])
  exit()
  
K -= len(margin)
K %= len(cycle)

print(cycle[K])

Submission status: Accepted

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

t,i,dist=0,0,{0:0}
while K>0:
    K,i,t=K-1,i+1,A[t]
    if t in dist:
        K%=i-dist[t]
    else:
        dist[t]=i

print(t+1)

Submission status: Accepted

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

t,i,dist=0,0,{0:0}
while K>0:
    K-=1
    i+=1
    t=A[t]
    if t in dist:
        K%=i-dist[t]
    else:
        dist[t]=i

print(t+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
L = [-1] * (N+1)
L[1] = 0
idx = 1
for i in range(1, N+1):
    idx = A[idx]
    if L[idx] >= 0:
        t = i - L[idx]
        b = L[idx]
        break
    else:
        L[idx] = i

if K <= b:
    print(L.index(K))
else:
    print(L.index((K-b)%t+b))

Submission status: Accepted

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

dist={0:0}
t=i=0
while K>0:
    K-=1
    i+=1
    t=A[t]
    if t in dist:
        K%=i-dist[t]
    else:
        dist[t]=i

print(t+1)

Submission status: Accepted

Solution code:
from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
C = Counter([])
X, Y = [], []
m = 0
for _ in range(n):
    a = A[m]-1
    C[m] += 1
    X.append(m)
    if C[a] != 0:
        Y = X[X.index(a):]
        X = X[:X.index(a)]
        break
    m = a
# print(X,Y)
x = len(X)
y = len(Y)
if k <= x-1:
    print(X[k]+1)
else:
    k -= x
    print(Y[k-(k//y)*y]+1)

Submission status: Accepted

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

seen={0}
town=0
while K>0:
    town=A[town]
    K-=1
    if town in seen:
        break
    seen.add(town)

start=town
i=0
while K>0:
    town=A[town]
    i+=1
    K-=1
    if town is start:
        break

K=K%i if i>0 else 0
while K>0:
    town=A[town]
    i+=1
    K-=1

print(town+1)

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    c = [[0]*(N+1) for _ in range(61)]
    c[0][1:] = A[:]
    for i in range(60):
        for j in range(1, N+1):
            c[i+1][j] = c[i][c[i][j]]
    i = 1 << 60
    j = 1
    k = 60
    while K > 0:
        if i <= K:
            K -= i
            j = c[k][j]
        i >>= 1
        k -= 1
    print(j)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    vis = [0 for i in range(n)]
    vis[0] = 1
    fst = [1]
    st = a[0]-1
    while True:
        if vis[st] == 0:
            vis[st] = 1
            fst.append(st+1)
            st = a[st]-1
        else:
            st = fst.index(st+1)
            loop = fst[st:]
            break
    if k < len(fst):
        print(fst[k])
    else:
        k = k - len(fst) + 1
        k = k%len(loop)
        print(loop[k-1])
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

machi = 1
road = [0,1]
Keiyu = [0]*(N+1)

for n in range(1, N+1):
    if Keiyu[machi] == 0:
        Keiyu[machi] = n
        road.append(A[machi])
        machi = A[machi]
    else:
        S = Keiyu[machi] - 1
        E = n - 1
        break

#print(road)
#print(Keiyu)
#print(S)
#print(E)

if K <= S:
    print(road[K+1])
else:
    K = K - S
    K = S + K % (E-S)
    print(road[K+1])

Submission status: Accepted

Solution code:
import sys

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

for i in range(n):
    a[i]-=1
#print(a)

if k<=n:
    b=0
    for i in range(k):
        b=a[b]
    print(b+1)
    sys.exit()
    
b=0
c=[-1]*n
c[0]=0
for i in range(n):
#   print(b,a[b])
   b=a[b]
   if c[b]>=0:
#       print("i:",i)
       break
   else:
       c[b]=i+1

ki=c[b]+1
kc=(i+1)-c[b]
k2=(k-ki)%kc+ki
#print("ki:",ki,"kc:",kc,"k2:",k2)
b=0
for i in range(k2):
    b=a[b]
print(b+1)

Submission status: Accepted

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

visited = [0] * (N + 1)
route = [0] * (N + 1)
next_ = 1
count = 0

for i in range(K + 1):
    if visited[next_] != 0:
        x = visited[next_]
        count = (K - (x - 1)) % (i + 1 - x) + x
        print(route[count])
        exit()
    visited[next_] = i + 1
    route[i + 1] = next_
    next_ = A[next_]

print(route[K + 1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc167/tasks/abc167_d
# コンテスト中は周期性を用いたが、今回はdoublingで解いてみる

import sys
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, read().split()))


N, K = ints()
A = mina(*ints())
# 10^18のは60bitで表せるのでnxt tableをつくるのに最大1.2 * 10^7 ぐらい。ギリ間に合いそう


nxt = [[-1] * N for _ in ra(K.bit_length())]  # [k][v]...vから2^k回移動したノード
# 初期化
for v, nx in enu(A):
    nxt[0][v] = nx

# テーブル埋め
for k in ra(K.bit_length() - 1):
    for v in ra(N):
        nxt[k + 1][v] = nxt[k][nxt[k][v]]

# 答えの取得
now = 0  # はじめは0地点にいる
for k in ra(K.bit_length()):
    if (K >> k) & 1:
        # kbit目が立ってたらこの回数分だけ移動
        now = nxt[k][now]
print(now + 1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc167/tasks/abc167_d
# コンテスト中は周期性を用いたが、今回はdoublingで解いてみる

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def ints(): return list(map(int, read().split()))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N, K = ints()
A = mina(*ints())
# 10^18のは60bitで表せるのでnxt tableをつくるのに最大1.2 * 10^7 ぐらい。ギリ間に合いそう


nxt = [[-1] * N for _ in ra(K.bit_length())]  # [k][v]...vから2^k回移動したノード
# 初期化
for v, nx in enu(A):
    nxt[0][v] = nx

# テーブル埋め
for k in ra(K.bit_length() - 1):
    for v in ra(N):
        nxt[k + 1][v] = nxt[k][nxt[k][v]]

# 答えの取得
now = 0  # はじめは0地点にいる
for k in ra(K.bit_length()):
    if (K >> k) & 1:
        # kbit目が立ってたらこの回数分だけ移動
        now = nxt[k][now]
print(now + 1)

Submission status: Accepted

Solution code:
def solve():
    N, K = map(int, input().split())
    A = [0]+list(map(int, input().split()))
    visited = [-1]*(N+1)
    visited[1] = 0
    now = 1
    for i in range(1,K+1):
        now = A[now]
        if visited[now]>=0:
            break
        visited[now] = i
    if i==K:
        ans = now
    else:
        num = (K-visited[now])%(i-visited[now])+visited[now]
        ans = visited.index(num)
    return ans
print(solve())

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
n += 1
a = [0] + LIST()
# b[1]: 町iに到達する最小回数
b = [-1]*n

now = 1
count = 0
for i in range(n):
    if b[now] == -1:
        b[now] = count
        count += 1
        now = a[now]
    else:
        offset = b[now]
        loop = count - b[now]
        break
if k <= offset:
    targ = k
else:
    targ = (k-offset) % loop + offset

for i in range(1, n):
    if b[i] == targ:
        print(i)
        exit()

Submission status: Accepted

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

X = [-1 for _ in range(N)]
X[0] = 0

k = 0
p = 0
while k < K:
    p = A[p]
    k += 1
    if X[p] != -1:
        v = (K - k) % (k - X[p]) + X[p]
        print(X.index(v) + 1)
        exit(0)
    X[p] = k
print(p + 1)

Submission status: Accepted

Solution code:
from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
for i in range(N):
    B.append(A[B[i]-1])

S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
k_s = None

while k < N:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
        cnt += 1
    k += 1
if k_s and k_s < K:
    k_max = (K - B.index(idx)) % (k_s - k_f) + B.index(idx)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)

Submission status: Accepted

Solution code:
from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
while k <= N:
    i = A[i] - 1
    B.append(i + 1)
    k += 1
S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
k_s = None
while k < N:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
        cnt += 1
    k += 1
if k_s and k_s < K:
    k_max = (K - B.index(idx)) % (k_s - k_f) + B.index(idx)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)

Submission status: Accepted

Solution code:
from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
while k <= 10 ** 6:
    i = A[i] - 1
    B.append(i + 1)
    k += 1
S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
k_s = None
while k < 10 ** 6:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
        cnt += 1
    k += 1
if k_s and k_s < K:
    k_max = (K - B.index(idx)) % (k_s - k_f) + B.index(idx)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
ls = list(map(int,input().split()))
fi = [-1]*(n+1)
fi[1] = 0
a = 0
aa = 0
for i in range(k):
    if fi[ls[a]] == -1:
        fi[ls[a]] = i + 1
        aa = a
        a = ls[a] - 1
    else:
        ind = fi[ls[a]]
        t = (k - ind) % (max(fi) + 1 - ind)
        t += ind
        print(fi.index(t))
        break
else:
    print(ls[aa])

Submission status: Accepted

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

mrk = [0] * n
plc = a[0] - 1
rp = 0 #ループに入った場所
rpc = -1#ループに入ってから
prc = 0#ループに入る前
for i in range(1, k + 1):
#    logging.debug(i)
    if rpc >= 0:
        rpc += 1
        if plc == rp:
#            logging.debug("prc{},rpc{}".format(prc,rpc))
            k = (k - prc) % rpc
#            logging.debug("k{},plc{}".format(k,plc))
            for i in range(k):
                plc = a[plc] - 1
#                logging.debug(plc)
            print(plc + 1)
            exit()
    if rpc == -1:
        prc += 1
    if mrk[plc] == 1 and rpc == -1:
        rp = plc
        rpc = 0
    mrk[plc] += 1
    if i < k:
        plc = a[plc] - 1
#    logging.debug("{},next{},{},roop{}".format(mrk,plc,prc,rpc))

print(plc + 1)

Submission status: Accepted

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

check = [0] * N
time = [-1] * N
check[0] = 1
time[0] = 0
now = 1
t = 1
ex = 0
roop = 0
for i in range(N + 1):
  now = A[now - 1]
  if check[now - 1] == 0:
    check[now - 1] = 1
    time[now - 1] = t
  else:
    ex = time[now - 1]
    roop = t - time[now - 1]
    break
  t += 1
  
if K < t:
  ans = time.index(K) + 1
  print(ans)
else:
  K -= (t - 1)
  K %= roop
  if K == 0:
    K = roop
  #print(K)
  ans = time.index(ex + K - 1) + 1
  print(ans)
  #print(check, time, roop, t, ex)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    
    now = 1
    check = [0] * n
    check[0] = 1
    move = [1]
    for i in range(k):
        now = a_list[now-1]
        move.append(now)
        if check[now-1] == 0:
            check[now-1] = 1
        else: 
            break

    point = (move.index(now))
    roop_len = sum(check) - point

    if k <= sum(check):
        print(move[k])
    else:
        k_ = k - point
        point_ = k_ % roop_len
        print(move[point+point_])

Submission status: Accepted

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

C=[0]*n
C[0]=1
c=0
loopc=0
i=0
io=0
while c<k :
    newi = A[i]-1
    C[newi]+=1
    if C[newi]>=3 :
        rs=newi
        break
    elif C[newi]==2 :
        loopc+=1
    io=i
    i=newi
    c+=1

if (k-c)<0 or loopc==0 :
    print(i+1)
    exit()
mod = (k-c)%(loopc)
# print( k, c, loopc, i, mod)


# i=rs
while mod>0 :
    newi = A[i]-1
    i=newi
    mod-=1

print( i+1 )

Submission status: Accepted

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

    route = [1]
    route_set = set(route)
    towns_step = [0] * (N+10)
    step = 0
    now = 1
    while A[now] not in route_set:
        next = A[now]
        route.append(next)
        route_set.add(next)
        step += 1
        towns_step[next] = step
        now = next

    border = towns_step[A[now]]
    head = route[0: border]
    roop = route[border:]

    if K < border:
        ans = head[K]
    else:
        k = (K - border) % len(roop)
        ans = roop[k]
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import copy

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

dist = [-1] * (n+1)
dist[1] = 0

cn = 1
d = 0
cycle = 0
while True:
    d += 1
    nn = a[cn]
    if d == k:
        ans = nn
        break
    if dist[nn] == -1:
        dist[nn] = copy.deepcopy(d)
    elif cycle == 0:
        cycle = d - dist[nn]
        k = (k - d) % cycle + d
    if d == k:
        ans = nn
        break
    cn = nn

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, k, *a = map(int, read().split())

    cur_town = 0
    tran_time = defaultdict(int)
    cnt = 0
    while True:
        if k == 0:
            print(cur_town + 1)
            sys.exit()
        if cur_town in tran_time:
            break
        else:
            tran_time[cur_town] = cnt
            cur_town = a[cur_town] - 1
            cnt += 1
            k -= 1
    k2 = k % (cnt - tran_time[cur_town])
    while k2 > 0:
        k2 -= 1
        cur_town = a[cur_town] - 1
    print(cur_town + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

j=1
step=0
s=set([])
l=[]
loop_s=-1
loop_g=-1

while True:
	s.add(j)
	l+=[j]
	j=a_ls[j-1] #update
	if j in s:
		loop_s=l.index(j)
		loop_g=len(l)
		break


#print(l)
#print(loop_s)
#print(loop_g)

if K<loop_s:
	print(l[K])
elif (K+1-loop_s)%(loop_g-loop_s)!=0:
	print(l[loop_s+(K+1-loop_s)%(loop_g-loop_s)-1])
else:
	print(l[-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, k, *a = map(int, read().split())

    cur_town = 0
    transits = set()
    tran_time = defaultdict(int)
    cnt = 0
    while True:
        if k == 0:
            print(cur_town + 1)
            sys.exit()
        if cur_town in transits:
            break
        else:
            transits.add(cur_town)
            tran_time[cur_town] = cnt
            cur_town = a[cur_town] - 1
            cnt += 1
            k -= 1
    k2 = k % (cnt - tran_time[cur_town])
    while k2 > 0:
        k2 -= 1
        cur_town = a[cur_town] - 1
    print(cur_town + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

# k: number of transfer
_,k = LI()
a = LI()
# 街の番号を0始まりに変更
a = list(map(lambda x:x-1,a))
# print(a)

s = set([0])

# 再帰関数
def rec(visited,next):
    if next in s:
        # print(visited)
        return visited,visited.index(next)
    else:
        s.add(next)
        visited.append(next)
        return rec(visited,a[next])

visited = [0]
# 訪れた街、初めて2度訪れた街のインデックスを取得
visited,loopStart = rec(visited,a[0])

# print(visited,loopStart)

if k < len(visited):
    townIndex = visited[k]
else:
    visitedLoop = visited[loopStart:]
    # print(visitedLoop)
    # 残り回数を循環配列の長さで割った余り
    index = (k-(loopStart))%len(visitedLoop)
    # print(index)
    townIndex = visitedLoop[index]

print(townIndex+1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_, k = Is()
towns = [i-1 for i in Is()]

now = 0
seen = [0]
seenx = {0: 0}

while k > 0:
  k -= 1
  now = towns[now]
  
  if now not in seenx:
    seenx[now] = len(seen)
    seen.append(now)
  else:
    seen = seen[seenx[now]:]
    break

if k == 0:
  print(1 + now)
else:
  print(1 + (seen[k % len(seen)]))

Submission status: Accepted

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

s = []
ord = [-1] *(n+1)
c = 0

v = 1
while ord[v] == -1:
    ord[v] = len(s)
    s.append(v)
    v = a[v]

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:
n,k,*aa = map(lambda x:int(x)-1, open(0).read().split())
n += 1
k += 1
passed = set()

i = 0
while k and i not in passed:
    k -= 1
    passed.add(i)
    i = aa[i]

if k:
    fst = i
    cycle = [fst]
    i = aa[i]

    while i != fst:
        cycle.append(i)
        i = aa[i]
    ans = cycle[k%len(cycle)]
else:
    ans = i
print(ans+1)

Submission status: Accepted

Solution code:

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

lim = 100
dp = [[0] * (N + 1) for _ in range(lim)]
dp[0] = [0] + X
for k in range(1, lim):
    for i in range(N + 1):
        dp[k][i] = dp[k - 1][dp[k - 1][i]]

ans = 1
for i in range(lim):
    if K >> i & 1:
        ans = dp[i][ans]

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 * 2)
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
top = -1
hist = []
finished = [True] + [False for _ in range(N)]
seen = [True] + [False for _ in range(N)]

def dfs(cur):
    global hist, finished, seen, top
    hist.append(cur)
    seen[cur] = True
    nex = A[cur]
    if seen[nex] and not finished[nex]:
        top = nex
        return
    dfs(nex)
    if not top == -1:
        return
    hist.pop()
    finished[cur] = True
    
dfs(1)
cycle = []
while not hist == []:
    i = hist.pop()
    cycle.append(i)
    if i == top:
        break

cycle.reverse()

cur = 1
while not cur == top and not K == 0:
    cur = A[cur]
    K -= 1

if cur == top:
    cur = cycle[K % len(cycle)]

print(cur)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
t={1:0}
g={0:1}
c,d=1,0
while d!=k:
    d+=1
    c=a[c-1]
    if c in t:
        print(g[t[c]+(k-t[c])%(d-t[c])])
        exit()
    else:
        t[c]=d
        g[d]=c
print(c)

Submission status: Accepted

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

journey = [1]

for i in range(n):
    journey.append(a[journey[i]])

if k <= n:
    print(journey[k])
    exit()

cycle_end = n
cycle_start = n - 1

while journey[cycle_start] != journey[cycle_end]:
    cycle_start -= 1

cycle_range = cycle_end - cycle_start

cycle_cnt = (k - n) // cycle_range
extra = (k - n) - (cycle_range * cycle_cnt)

for i in range(extra):
    journey.append(a[journey[i + n]])    

print(journey[-1])

Submission status: Accepted

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
alist=[]
cnt=0
i=1
blist=[0]*(n+1)
while blist[a[i-1]]==0:
  i=a[i-1]
  alist.append(i)
  blist[i]=1
  cnt+=1
loop1=alist.index(a[i-1])
if k<loop1+1:
  print(alist[k-1])
else:
  print(alist[((k-loop1-1)%(cnt-loop1))+loop1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
visit=[0 for i in range(n)]
goal,loop=[],[]
now=0

while visit[now]!=2 :
    if visit[now]==0 :
        goal.append(now)
    else :
        loop.append(now)
    visit[now]+=1
    now=a[now]-1

if len(goal)>k :
    print(goal[k]+1)
else :
    res=len(goal)-len(loop)
    print(loop[(k-res)%len(loop)]+1)