提出 c95d6e43-9015-4a85-8c41-ceee869c742a

コード

import math
import bisect
import collections
import heapq
#import sys
#import decimal
#import random

def main():
    n,q = map(int,input().split())
    logk = 30
    # C++の解説のinputに相当する
    get = 0
    doubling = [[-1]*n for i in range(logk)]
    fill = [[] for _ in range(logk * n)]
    dist = [-1]*n
    ex = 1
    unknown = 0
    for _ in range(q):
        case, x, y = map(int,input().split())
        if case == 1:
            x -= 1
            y -= 1
            if (doubling[0][x] == y):
                continue
            get += 1
            doubling[0][x] = y
            que = collections.deque()
            que.append(logk * x)
            while que:
                a = que[0] % logk
                b = que[0] // logk
                que.popleft()
                if a != 0:
                    doubling[a][b] = doubling[a-1][doubling[a-1][b]]
                if doubling[a][b] == -1:
                    fill[logk * doubling[a-1][b] + a - 1].append(logk * b + a)
                    continue
                elif a == logk - 1:
                    continue
                que.append(logk * b + a + 1)
                for i in fill[logk * b + a]:
                    que.append(i)
            if get == n - 1:
                rev = [[] for _ in range(n)]
                next = collections.deque()
                for i in range(n):
                    if doubling[0][i] == -1:
                        unknown = i
                    else:
                        rev[doubling[0][i]].append(i)
                next.append(unknown)
                dist[unknown] = 0
                while next:
                    # C++の解答のgoto文を再現するための真偽値
                    tf = False
                    for i in rev[next[0]]:
                        if dist[i] > -1:
                            dist[i] = -1
                            tf = True
                            break
                        dist[i] = dist[next[0]] + 1
                        next.append(i)
                    if tf:
                        break
                    next.popleft()
                maxi = 0
                for i in dist:
                    if i < 0:
                        maxi = 200000
                    maxi = max(maxi,i)
                for i in range(maxi+1):
                    ex = math.lcm(ex, i + 1)
                    if ex > 1000000000:
                        break
        else:
            x -= 1
            if (get == n - 1) and (y > dist[x]) and ((y - dist[x]) % ex == 0):
                print(unknown + 1)
                continue
            now = x
            cnt = 0
            while y > 0:
                if y % 2 == 1:
                    now = doubling[cnt][now]
                if now == -1:
                    break
                cnt += 1
                y //= 2
            if now == -1:
                now -= 1
            print(now + 1)
    return

main()

結果

問題	点数	言語	結果	実行時間	メモリ
S. Association	20	Python3 (CPython)	TLE	6087 ms	144896 KiB

テストセット

テストセット	結果	得点	実行時間	メモリ
testcase1	AC × 20	20	46 ms	10368 KiB
testcase2	AC × 9 TLE × 3	0	5882 ms	144896 KiB
testcase3	AC × 27 TLE × 8	0	6087 ms	144896 KiB

詳細結果

テストケース	結果	実行時間	メモリ
sub1sub2sub3_hand_01.txt	AC	35 ms	10240 KiB
sub1sub2sub3_hand_02.txt	AC	36 ms	10240 KiB
sub1sub2sub3_hand_03.txt	AC	35 ms	10240 KiB
sub1sub2sub3_random_01.txt	AC	35 ms	10368 KiB
sub1sub2sub3_random_02.txt	AC	39 ms	10368 KiB
sub1sub2sub3_random_03.txt	AC	37 ms	10368 KiB
sub1sub3_corner_01.txt	AC	46 ms	10112 KiB
sub1sub3_corner_02.txt	AC	35 ms	10240 KiB
sub1sub3_corner_03.txt	AC	33 ms	10240 KiB
sub1sub3_corner_04.txt	AC	43 ms	10240 KiB
sub1sub3_corner_05.txt	AC	37 ms	10368 KiB
sub1sub3_corner_06.txt	AC	35 ms	10240 KiB
sub1sub3_corner_07.txt	AC	35 ms	10368 KiB
sub1sub3_example_01.txt	AC	36 ms	10368 KiB
sub1sub3_example_02.txt	AC	38 ms	10240 KiB
sub1sub3_hand_04.txt	AC	39 ms	10368 KiB
sub1sub3_hand_05.txt	AC	38 ms	10368 KiB
sub1sub3_random_04.txt	AC	38 ms	10368 KiB
sub1sub3_random_05.txt	AC	36 ms	10240 KiB
sub1sub3_random_06.txt	AC	36 ms	10240 KiB
sub2sub3_max_01.txt	TLE	5882 ms	144896 KiB
sub2sub3_max_02.txt	TLE	5659 ms	144384 KiB
sub2sub3_max_03.txt	TLE	5657 ms	144896 KiB
sub2sub3_random_07.txt	AC	3056 ms	120192 KiB
sub2sub3_random_08.txt	AC	3871 ms	77056 KiB
sub2sub3_random_09.txt	AC	2006 ms	30336 KiB
sub3_corner_08.txt	AC	4909 ms	36352 KiB
sub3_corner_09.txt	AC	4989 ms	49408 KiB
sub3_corner_10.txt	TLE	5264 ms	49280 KiB
sub3_max_04.txt	TLE	6018 ms	8192 KiB
sub3_max_05.txt	TLE	6054 ms	7808 KiB
sub3_max_06.txt	TLE	6087 ms	8320 KiB
sub3_random_10.txt	AC	3414 ms	68096 KiB
sub3_random_11.txt	AC	3837 ms	80768 KiB
sub3_random_12.txt	TLE	5586 ms	141568 KiB