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:
# https://atcoder.jp/contests/abc167/tasks/abc167_d


'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

import sys
input = sys.stdin.readline
import marshal

class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edge
        else:
            edge2 = marshal.loads(marshal.dumps(self.edge))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    # return t + 1
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info

    def cycle_detector(self, start, time=0, save=False):
        """
        :param p: スタート地点
        :param save: True = 前回の探索結果を保持する
        :return: 各点までの距離と何番目に発見したかを返す
        """


        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edge
        else:
            edge2 = marshal.loads(marshal.dumps(self.edge))

        p, t = start, time
        self.parent[p] = -2
        cycle_end = False
        cycle_time = 0
        cycle = []
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    if not cycle:
                        if q == p:
                            """ 自己ループの時 """
                            cycle.append(q + self.decrement)
                            cycle_end = True
                        else:
                            cycle.append(q + self.decrement)
                            cycle.append(p + self.decrement)
                            cycle_time = t

                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """
                if cycle and t == cycle_time - 1 and not cycle_end:
                    if cycle[0] == p + self.decrement:
                        cycle_end = True
                        continue
                    cycle.append(p + self.decrement)
                    cycle_time = t

                """"""""""""""""""""
        cycle = list(reversed(cycle))
        return [cycle[-1]] + cycle[:-1]

    def tree_counter(self, detail=False):
        """
        :param detail: True = サイクルのリストを返す
        :return: 木（閉路を含まない）の個数を返す
        """
        self.parent = [-1] * self.n

        connection_number = 0
        cycle_list = []

        for p in range(self.n):
            if self.parent[p] == -1:
                connection_number += 1
                cycle = self.cycle_detector(p + self.decrement, save=True)
                if cycle:
                    cycle_list.append(cycle)
        if not detail:
            return connection_number - len(cycle_list)
        else:
            return cycle_list
##################################################################


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

M = N
graph = Graph(N,dictated=True,destroy=True)
for i in range(1,M+1):
    x = i
    y = A[i-1]
    graph.add_edge(x, y)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(graph.cycle_detector(1))
    len_cycle = len(cycle)
    p = 0
    cnt = 0
    res = 0
    while p != cycle[0] - 1:
        p = A[p] - 1
        cnt += 1
    k = (K - cnt) % len_cycle
    res = cycle[k]
print(res)

Submission status: Accepted

Solution code:
#####################################################################################################
##### 深さ優先探索 幅優先探索　（グラフ）
#####################################################################################################

'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
from copy import deepcopy



class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def cycle_detector(self, start, time=0, save=False):
        """
        :param p: スタート地点
        :param save: True = 前回の探索結果を保持する
        :return: 各点までの距離と何番目に発見したかを返す
        """

        edge2 = deepcopy(self.edge)

        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n

        p, t = start, time
        self.parent[p] = -2
        cycle_end = False
        cycle_time = 0
        cycle = []
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    if not cycle:
                        if q == p:
                            """ 自己ループの時 """
                            cycle.append(q + self.decrement)
                            cycle_end = True
                        else:
                            cycle.append(q + self.decrement)
                            cycle.append(p + self.decrement)
                            cycle_time = t

                    """"""""""""""""""""
                    continue
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """
                if cycle and t == cycle_time - 1 and not cycle_end:
                    if cycle[0] == p + self.decrement:
                        cycle_end = True
                        continue
                    cycle.append(p + self.decrement)
                    cycle_time = t

                """"""""""""""""""""
        cycle = list(reversed(cycle))
        return [cycle[-1]] + cycle[:-1]

    def tree_counter(self, detail=False):
        """
        :param detail: True = サイクルのリストを返す
        :return: 木（閉路を含まない）の個数を返す
        """
        self.parent = [-1] * self.n

        connection_number = 0
        cycle_list = []

        for p in range(self.n):
            if self.parent[p] == -1:
                connection_number += 1
                cycle = self.cycle_detector(p + self.decrement, save=True)
                if cycle:
                    cycle_list.append(cycle)
        if not detail:
            return connection_number - len(cycle_list)
        else:
            return cycle_list

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.dictated:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y in self.edge[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        nx.draw_networkx(G)
        plt.show()

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


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

M = N
graph = Graph(N,dictated=True)
for i in range(1,M+1):
    x = i
    y = A[i-1]
    graph.add_edge(x, y)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(graph.cycle_detector(1))
    len_cycle = len(cycle)
    p = 0
    cnt = 0
    res = 0
    while p != cycle[0] - 1:
        p = A[p] - 1
        cnt += 1
    k = (K - cnt) % len_cycle
    res = cycle[k]
print(res)

Submission status: Accepted

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

now = 1
visited = []
visited_set = set()

for i in range(1, K+1):
    visited.append(now)
    visited_set.add(now)
    now = A[now]
    if now in visited_set:
        loop_start = visited.index(now)
        loop_length = i - loop_start
        print(visited[loop_start + (K - loop_start) % loop_length])
        break
else:
    print(now)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.insert(0, None)

history = [None] * (N+1)

next_town = 1
i = 0
skip_flg = False
while i < K:
  if history[next_town] == None:
    history[next_town] = i
  elif skip_flg == False:
    skip_flg = True
    
    i = i + ((K - i)//(i - history[next_town])) * (i - history[next_town])
  if i < K:
    i += 1
    next_town = A[next_town]
print(next_town)

Submission status: Accepted

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

b = [0]*n
r = [0]*n
index = 0
for i in range(1,n+1) :
    if b[a[index]-1] != 0 :
        break
    b[a[index]-1] = i
    index = a[index] - 1

for i in range(1,n+1) :
    if r[a[index]-1] != 0 :
        break
    r[a[index]-1] = i
    index = a[index] - 1

maxb = max(b)
maxr = max(r)
if k <= maxb :
    print(b.index(k)+1)
else :
    k = k - maxb
    if k%maxr == 0 :
        print(r.index(maxr)+1)
    else :
        print(r.index(k%maxr)+1)

Submission status: Accepted

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

now = 1
visited = []
visited_set = set()
flag = False

for i in range(1, K+1):
    visited.append(now)
    visited_set.add(now)
    now = A[now]
    if now in visited_set:
        loop_start = visited.index(now)
        loop_length = i - loop_start
        flag = True
        break
else:
    print(now)

if flag:
    print(visited[loop_start + (K - loop_start) % loop_length])

Submission status: Accepted

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

now = 1
visited = []
visited_set = set()

for i in range(1, N+1):
    visited.append(now)
    visited_set.add(now)
    now = A[now]
    if now in visited_set:
        loop_start = visited.index(now)
        loop_length = i - loop_start
        break

if K >= loop_start:
    print(visited[loop_start + (K - loop_start) % loop_length])
else:
    print(visited[K])

Submission status: Accepted

Solution code:
#####################################################################################################
##### 深さ優先探索 幅優先探索　（グラフ）
#####################################################################################################

'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline



def bfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


def connection_counter(conj):                   # conj の連結成分の個数を返す。関数 bfs が必要
    cnt = 0
    visit = set()
    for start in range(N):
            if start not in visit:
                cnt += 1
                bfs(start, conj, visit)
    return cnt


def distance_list(conj, start, visit=set()):    # スタート地点からの距離の全列挙
    dist = [0]*N
    visit.add(start)
    next_set = deque([(start, 0)])
    while next_set:
        p, t = next_set.popleft()
        for q in conj[p]:
            if q in visit:
                continue
            dist[q] = t+1
            visit.add(q)
            next_set.append((q, t + 1))
    return dist


def dfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = [(start, 0)]                     # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.pop()                   # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられるる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1

#############################################################
# キャッシュにメモしながら動的計画法を行う場合など、
# 帰りがけ時に子ノードたちの結果をまとめるような処理が重要な場合には、
# 再帰関数を用いた DFS が簡明 (メモ化再帰)。
#############################################################


def dfs2(conj, p=0, goal=None, t=0, past_p=None, visit=set(), second_visit=set()):
    # global res
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        if q == goal:
            # ゴール時の処理
            # return t+1
            continue
        # p から q への引継ぎ処理
        # res[q] += res[p]
        dfs2(conj, q, goal, t+1, p, visit, second_visit)
    second_visit.add(p)
    # 帰り際の処置（壊した道を元に戻す等)
    # visit.discard(p)
    return # res


def cycle_detector(conj, p=0, t=0, dictated=False, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[]):
    visit.add(p)
    path.append(p)
    for q in sorted(conj[p]):
        if not dictated:
            if q == past_p:
                continue
        if q in second_visit:
            continue
        if q in visit:
            if not cycle:
                while path:
                    r = path.pop()
                    cycle.append(r)
                    if r == q:
                        break
            continue
        cycle_detector(conj, q, t+1, dictated, p, path, visit, second_visit, cycle)
    second_visit.add(p)
    return cycle


def tree_counter(conj, detail=False):           # 木（閉路を含まない）の個数を返す。detail = True で、閉路のリストを返す
    connection_number = 0
    cycle_list = []
    visit = set()
    second_visit = set()
    for start in range(N):
        if start not in visit:
            connection_number += 1
            cycle = cycle_detector(conj, start, visit=visit, second_visit=second_visit, cycle=[])
            if cycle:
                cycle_list.append(cycle)
    if not detail:
        return connection_number - len(cycle_list)
    else:
        return cycle_list


def path_detector(conj, p=0, t=0, past_p=None, full_path=[], visit=set(), second_visit=set(), decrement=False):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    full_path.append((p + decrement,t))
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            continue
        path_detector(conj, q, t+1, p, full_path, visit, second_visit, decrement)
    second_visit.add(p)
    full_path.append((p + decrement,t))
    return full_path

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


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

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


M = N
conj = [set() for _ in range(N)]
for i in range(M):
    u = i
    v = A[i] - 1
    conj[u].add(v)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(
        reversed(cycle_detector(conj, p=0, t=0, dictated=True, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[])))
    len_cycle = len(cycle)

    p = 0
    cnt = 0
    res = 0
    if not len_cycle:
        while cnt < K:
            p = A[p] - 1
            cnt += 1
        res = p + 1
    else:
        while p != cycle[0]:
            p = A[p] - 1
            cnt += 1
        k = (K - cnt) % len_cycle
        res = cycle[k] + 1
print(res)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lst = [0] + list(map(int, input().split()))
dic = {1:0}
loc = 1
for i in range(1, k + 1):
  loc = lst[loc]
  if loc not in dic:
    dic[loc] = i
  else:
    span = i - dic[loc]
    initial = dic[loc]
    z = (k - initial) % span
    for j in range(z):
      loc = lst[loc]
    print(loc)
    exit()
print(loc)

Submission status: Accepted

Solution code:
# D - Teleporter
N,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
s = {1:0}
l = [1]
i = 1
for j in range(1,10**10):
    i = A[i]
    if i in s:
        sigma = j-s[i]
        break
    s[i] = j
    l.append(i)
if K<s[i]:
    print(l[K])
else:
    K -= s[i]
    mod = l[s[i]:]
    print(mod[K%sigma])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
s = 1
B = []
set_ = set()
for i in range(N):
    if A[s-1] not in set_:
        set_.add(A[s-1])
        B.append(A[s-1])
        s = A[s-1]
        
    else:
        e = i
        break
idx = B.index(A[s-1])
if K-1<idx: print(B[K-1])
else:
    print(B[idx + (K-idx-1)%(e-idx)])

Submission status: Accepted

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

town = 1
once = [0]*(n+1)

for i in range(n):
  if once[town]==0:
    once[town] = 1
  else:
    break
  town = A[town]

rt = A[town]
roop = 1
while rt != town:
  rt = A[rt]
  roop += 1

rt = 1
bf = 0
while rt != town:
  rt = A[rt]
  bf += 1  

if bf<k:
  K = (k-bf)%roop + bf
else:
  K = k

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

print(town)

Submission status: Accepted

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

num =1
li = [1]
flag = [True]*n
flag[0] = False

for i in range(k):
    num = a[num-1]
    if flag[num-1]:
        li.append(num)
        flag[num-1] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d
print(li[ans])

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:
# Problem D - Teleporter

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

# initialization
visit_list = [0] * N
pos = a_list[0]
visit_list[pos-1] = 1
visit_count = 1
remain = K - 1
is_ok = True
ans = 0

# count
while remain>0 and is_ok:
    pos = a_list[pos-1]
    remain -= 1
    visit_count += 1
    if pos==1 or not visit_list[pos-1]==0:
        tmp_1 = visit_count - visit_list[pos-1]
        tmp_2 = remain % tmp_1
        for t in range(tmp_2):
            pos = a_list[pos-1]
        is_ok = False
        break
    else:
        visit_list[pos-1] = visit_count

# output
print(pos)

Submission status: Accepted

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

A = [[0 for _ in range(N+1)] for _ in range(100)]
A[0] = [0] + list(map(int, input().split()))

for l in range(1,100):
  #print(A[0])
  for j in range(1, N+1):
    #print(l,j)
    #print(l-1,A[l-1][j])
    A[l][j] = A[l-1][A[l-1][j]] #2^(l-1)1回テレポート後、さらに^(l-1)1回テレポート
  if 2 ** l > K:
    break

k = K
ans = 1
keta = 0
while k > 0:
  if k & 1:
    ans = A[keta][ans]
  k = k >> 1
  keta += 1

print(ans)

Submission status: Accepted

Solution code:
N, K = [int(_) for _ in input().split()]
A = [None] + [int(_) for _ in input().split()]
nowkaimin = [None] * (N + 1)
now = 1
kai = 0
nowkaimin[now] = kai
while True:
    now = A[now]
    kai += 1
    if kai == K:
        print(now)
        exit()
    if nowkaimin[now] is not None:
        break
    nowkaimin[now] = kai
#nowkaimin[now] to kai ga hitosii
#nowkaimin[now] + (kai - nowkaimin[now]) * Q + R
R = (K - nowkaimin[now]) % (kai - nowkaimin[now])
for i, v in enumerate(nowkaimin):
    if v == nowkaimin[now] + R:
        print(i)
        exit()

Submission status: Accepted

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

X = 0
town = 1
counted = [0 for _ in range(N)]
List = [0 for _ in range(N)]
for k in range(N):
  X += 1
  counted[k] = town
  town = A[town-1]
  if List[town-1] == 1:
    ini = counted.index(town)
    Q = X - ini
    break
  else:
    List[town-1] = 1
if K >= ini:    
  num = (K-ini) % Q
  print(counted[ini+num])
else:
  print(counted[K])

Submission status: Accepted

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

for i in range(k):
    now = a[now-1]
    # if now in path:
    #     now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
    #     break
    if alr[now-1] != 0:
        now = path[path.index(now) + (k-i-1)%(len(path) - path.index(now))]
        break
    path.append(now)
    alr[now-1] += 1

print(now)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
town=[0]*n
info=[1]
now=1
while town[now-1]==0:
    town[now-1]+=1
    now=a[now-1]
    info.append(now)
loop_list=list(info[info.index(now):-1])
loop_len=len(loop_list)
before_loop_list=list(info[:info.index(now)])
#print(town)
#print(info)
if k<len(before_loop_list):
    print(before_loop_list[k])
else:
    print(loop_list[((k-len(before_loop_list))%loop_len)])

Submission status: Accepted

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

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

judge = N*[0]
pos = 0
freq = 0

while judge[pos]==0 and K > 0:
	judge[pos] = 1
	pos = A[pos]
	K -= 1
	freq+=1

tmp = pos
pos = 0
while pos!=tmp:
	pos = A[pos]
	freq -= 1

#print(freq)
if K==0:
	print(pos+1)
else:
	K %= freq
	pos = tmp
	for i in range(K):
		pos = A[pos]
	print(pos+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

(n, k), s = map(int, input().split()), list(map(int, input().split()))
x, c = [1, s[0]], 0
for i in range(n): x.append(s[x[-1] - 1])
if len(x) > k: print(x[k]); exit()
while x[c] != s[x[-1] - 1]: c += 1
print(x[((k - c) % (len(x) - c)) + c])

Submission status: Accepted

Solution code:
import sys
def Ii():return int(sys.stdin.buffer.read())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n,k = Mi()
a = Li()
b = [1]
b.append(a[0])
flag = False
for i in range(n):b.append(a[b[-1]-1])
if len(b) > k:
  print(b[k])
  exit(0)
for j in range(len(b)):
  if b[j] == a[b[-1]-1]:
    break
    
roop = len(b)-j
roopk = (k-j)%roop
print(b[roopk+j])

Submission status: Accepted

Solution code:
#create date: 2020-07-03 11:44

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, k = na()
    a = na()
    visited_time = [-1] * n
    visited_time[0] = 0
    x, t = 0, 0
    while True:
        x = a[x] - 1
        t += 1
        if visited_time[x] > 0:
            b = visited_time[x]
            r = t - visited_time[x]
            break
        else:
            visited_time[x] = t
    if k <= b:
        print(visited_time.index(k) + 1)
    else:
        c = (k-b) % r
        print(visited_time.index(b+c) + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
town=[0]*n
info=[1]
now=1
while town[now-1]==0:
    town[now-1]+=1
    now=a[now-1]
    info.append(now)
loop_list=list(info[info.index(now):-1])
loop_len=len(loop_list)
before_loop_list=list(info[:info.index(now)])
if k<len(before_loop_list):
    print(before_loop_list[k])
else:
    print(loop_list[((k-len(before_loop_list))%loop_len)])

Submission status: Accepted

Solution code:
n,k = (int(a) for a in input().split())
A =  [-1] + list(map(int,input().split()))
t = [1]
flag =[0,1] + [0]*(n-1)
x = A[1]
while flag[x] == 0 :
    t.append(x)
    flag[x] = 1
    x = A[x] 

if k <= len(t) -1 :
    print(t[k])
else :
    l = t[t.index(x):]
    k = k - (len(t) - 1)
    k %= len(l)
    print(l[k-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
G = [[] for _ in range(N)]
for i, a in enumerate(map(int, input().split())):
    G[i] = a - 1
now = 0
seen = set()
#ループが始まる町とそれまでの移動回数iを求める
for i in range(1, K+1):
    seen.add(now)
    now = G[now]
    if now in seen:
        break
K -= i
if K > 0:
    #ループの移動回数jを求める。
    seen = set()
    for j in range(1,K+1):
        seen.add(now)
        now = G[now]
        if now in seen:
            break
    #ループの長さで割った余りｒを求める。
    r = K % j
    for _ in range(r):
        now = G[now]
print(now + 1)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N,K=MI()
A=[0]+LI()
c=1
turn=[-1]*(N+1)
for k in range(K):
  if turn[c]!=-1:
    T=k-turn[c]
    bias=turn[c]
    break
  turn[c]=k
  c=A[c]
else:
  print(c)
  exit()
K-=bias
K%=T
K+=bias
c=1
for k in range(K):
  c=A[c]
print(c)

Submission status: Accepted

Solution code:
import sys

def main():
    n, k = map(int, sys.stdin.buffer.readline().split())
    a = [0] + list(map(int, sys.stdin.buffer.readline().split()))

    visited = [0]*(n+1)
    town = 1
    for i in range(1, k+1):
        town = a[town]
        if visited[town] == 0:
            visited[town] = i
        else:
            cyc = (k - visited[town])%(i - visited[town]) + visited[town]
            print(visited.index(cyc))
            exit()
    print(town)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
turn = [-1] * (N+1) # いつ訪問したかを記録する
c = 1
for k in range(K):
    if turn[c]!=-1:
        T = k - turn[c] # 周期
        bias = turn[c] # バイアス
        break
    turn[c] = k
    c = A[c]
else:
    print (c)
    exit()

K -= bias 
K %= T
K += bias
c = 1 
for k in range(K):# 小さくしたKでシミュレーションし直す
    c = A[c]
print (c)

Submission status: Accepted

Solution code:
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))
d = {1: 0}
pre = 1
for i in range(1, N+1):
    new = A[pre-1]
    if d.get(new):
        roop_start = d[new]
        roop_end = i
        roop_pos = new
        break
    if i==K:
        print(new)
        sys.exit()
    d[new] = i
    pre = new

K -= roop_start
K %= roop_end-roop_start
pre = roop_pos
for i in range(K):
    pre = A[pre-1]
print(pre)