Submission #52699722

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import array
modBase = 998244353
n, q = map(int, input().split())
par = array.array("l", [-1 for _ in range (n+1)])
def redirect(x,y):
    while x >= 0:
        par[x], y, x = y, x, par[x]
x1 = 1
for _ in range(q):
    a, b, c = map(int, input().split())
    t = (a * x1 % modBase) % 2 + 1
    u = (b * x1 % modBase) % n + 1
    v = (c * x1 % modBase) % n + 1
    if t == 1:
        x = u
        y = v
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import array

modBase = 998244353

n, q = map(int, input().split())

par = array.array("l", [-1 for _ in range (n+1)])

def redirect(x,y):
    while x >= 0:
        par[x], y, x = y, x, par[x]

x1 = 1
for _ in range(q):
    a, b, c = map(int, input().split())
    t = (a * x1 % modBase) % 2 + 1
    u = (b * x1 % modBase) % n + 1
    v = (c * x1 % modBase) % n + 1
    if t == 1:
        x = u
        y = v
        while (x >= 0 and y >= 0):
            x = par[x]
            y = par[y]
        if x == -1:
            redirect(u,v)
        else:
            redirect(v,u)
    else:
        pb = par[u]
        pc = par[v]
        ppb = -1 if pb == -1 else par[pb]
        ppc = -1 if pc == -1 else par[pc]
        x1 = pb if ppb == v else pc if ppc == u else pb if pb == pc and pb != -1 else 0
        print(x1)
        x1 = x1 + 1

# オレ流マージテクで
# 実績あるアルゴリズムをPythonでも。

Submission Info

Judge Result