Submission #37129172

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class IntegerRelationUnionFind():
    def __init__(self, n):
        one = 2
        zero = 0
        add = lambda x, y: x + y
        minus = lambda x, y: x - y
        mult = lambda x, y: x * y // 2 if x * y % 2 == 0 else 1 // 0
        div = lambda x, a: x * 2 // a if x * 2 % a == 0 else 1 // 0
        randa = lambda: randrange(-2, 3, 4)
        randx = lambda: randrange(-10, 22, 2)
        self.n = n
        self.guf = GeneralRelationUnionFind(n, one, zero, add, minus, mult, div, randa, randx)
        # self.guf.check()
    
    def set_sum(self, i, j, s):
        # vi + vj = s
        ret = self.guf.unite(i, j, -2, s * 2)
        if self.guf.getvalue(i) is not None and self.guf.getvalue(i) % 2:
            return 0
        return ret
    def set_dif(self, i, j, s):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

class IntegerRelationUnionFind():
    def __init__(self, n):
        one = 2
        zero = 0
        add = lambda x, y: x + y
        minus = lambda x, y: x - y
        mult = lambda x, y: x * y // 2 if x * y % 2 == 0 else 1 // 0
        div = lambda x, a: x * 2 // a if x * 2 % a == 0 else 1 // 0
        randa = lambda: randrange(-2, 3, 4)
        randx = lambda: randrange(-10, 22, 2)
        self.n = n
        self.guf = GeneralRelationUnionFind(n, one, zero, add, minus, mult, div, randa, randx)
        # self.guf.check()
    
    def set_sum(self, i, j, s):
        # vi + vj = s
        ret = self.guf.unite(i, j, -2, s * 2)
        if self.guf.getvalue(i) is not None and self.guf.getvalue(i) % 2:
            return 0
        return ret
    def set_dif(self, i, j, s):
        # vj = vi + s
        ret = self.guf.unite(i, j, 2, s * 2)
        if self.guf.getvalue(i) is not None and self.guf.getvalue(i) % 2:
            return 0
        return ret
    def relation(self, i, j):
        a, b = self.guf.relation(i, j)
        return (a // 2, b // 2)
    def getvalue(self, i):
        ret = self.guf.getvalue(i)
        if ret is None:
            return None
        assert ret % 2 == 0
        return ret // 2
class PotentialUnionFind():
    def __init__(self, n):
        self.one = 1
        self.zero = 0
        self.add = lambda x, y: x + y
        self.minus = lambda x, y: x - y
        self.mult = lambda x, y: x * y
        self.div = lambda x, a: x // a
        self.randa = lambda: 1
        self.randx = lambda: randrange(-20, 21)
        self.n = n
        self.guf = GeneralRelationUnionFind(n, one, zero, add, minus, mult, div, randa, randx)
        # self.guf.check()
    
    def unite(self, i, j, s):
        # vj = vi + s
        ret = self.guf.unite(i, j, 1, s)
        return ret
    def diff(self, i, j):
        a, b = self.guf.relation(i, j)
        return b
    def getvalue(self, i):
        ret = self.guf.getvalue(i)
        if ret is None:
            return None
        return ret
    def setvalue(self, i, v):
        ret = self.guf.setvalue(i, v)
        return ret
    def same(self, i, j):
        ret = self.guf.same(i, j)
        return ret
class GeneralRelationUnionFind():
    def __init__(self, n, one, zero, add, minus, mult, div, randa = None, randx = None):
        self.one = one
        self.zero = zero
        self.add = add
        self.minus = minus
        self.mult = mult
        self.div = div
        self.randa = randa
        self.randx = randx
        self.n = n
        self.PA = [-1] * n
        self.rel = [(self.one, self.zero)] * n
        self.value = [None] * n
        self.contradiction = 0
        self.contradiction_str = "!"
    
    def check(self, m = 1000):
        for _ in range(m):
            x1 = self.randx()
            x2 = self.randx()
            x3 = self.randx()
            a1 = self.randa()
            
            # One Check
            assert self.mult(a1, self.one) == self.mult(self.one, a1) == a1
            
            # Zero Check
            assert self.add(x1, self.zero) == self.add(self.zero, x1) == x1
            assert self.minus(x1, self.zero) == x1
            
            # Minus Check
            assert self.add(self.minus(x1, x2), x2) == x1
            
            # Add
            assert self.add(x1, x2) == self.add(x2, x1)
            assert self.add(self.add(x1, x2), x3) == self.add(x1, self.add(x2, x3))
            
            # Mult
            assert self.mult(x1, x2) == self.mult(x2, x1)
            
            # Div
            assert self.mult(self.div(x1, a1), a1) == x1
            
            aa = self.minus(self.one, a1)
            if aa != self.zero:
                assert self.mult(self.div(x1, aa), aa) == x1
        
        print("Check OK !!!")
        
    def root(self, x):
        x0 = x
        sa, sb = self.one, self.zero
        while self.PA[x] >= 0:
            a, b = self.rel[x]
            sa, sb = self.mult(sa, a), self.add(self.mult(sa, b), sb)
            x = self.PA[x]
        return x, sa, sb
    def relation(self, x, y):
        rx, ax, bx = self.root(x)
        ry, ay, by = self.root(y)
        if rx == ry:
            return (self.div(ay, ax), self.minus(by, self.div(self.mult(ay, bx), ax)))
        else:
            return None
    def getvalue(self, x):
        rx, ax, bx = self.root(x)
        if self.value[rx] is None:
            return None
        if self.value[rx] == self.contradiction_str:
            return self.contradiction_str
        return self.add(self.mult(self.value[rx], ax), bx)
    def setvalue(self, x, v):
        vx = self.getvalue(x)
        if vx is not None:
            if vx == v:
                return 1
            rx, ax, bx = self.root(x)
            self.value[rx] = self.contradiction_str
            self.contradiction = 1
            return 0
        rx, ax, bx = self.root(x)
        self.value[rx] = self.div(self.minus(v, bx), ax)
        return 1
    def same(self, x, y):
        # 関係式に関係なく、通常 UF で連結かどうかを判定
        if self.root(x)[0] == self.root(y)[0]:
            return 1
        return 0
    def unite(self, x, y, a, b):
        # y = ax + b
        # 新たに矛盾が発生すれば 0 を返す
        rx, ax, bx = self.root(x)
        ry, ay, by = self.root(y)
        vx = self.getvalue(x)
        vy = self.getvalue(y)
        if vx == self.contradiction_str or vy == self.contradiction_str:
            if rx != ry:
                self.value[rx] = self.contradiction_str
                self.value[ry] = self.contradiction_str
                if self.PA[ry] >= self.PA[rx]:
                    self.PA[rx] += self.PA[ry]
                    self.PA[ry] = rx
                else:
                    self.PA[ry] += self.PA[rx]
                    self.PA[rx] = ry
        elif vx is None and vy is None:
            if rx == ry:
                aa = self.minus(self.mult(a, ax), ay)
                bb = self.minus(by, self.add(b, self.mult(a, bx)))
                if aa == self.zero:
                    if bb == self.zero:
                        # print("Consistent with prior information. Do nothing")
                        pass
                    else:
                        # print("NG")
                        self.contradiction = 1
                        self.value[rx] = self.contradiction_str
                        return 0
                else:
                    r = self.div(bb, aa)
                    self.value[rx] = r
                    # print("Value Identified", r)
            else:
                if self.PA[ry] >= self.PA[rx]:
                    self.PA[rx] += self.PA[ry]
                    self.rel[ry] = (self.div(self.mult(ax, a), ay), self.div(self.minus(self.add(self.mult(a, bx), b), by), ay))
                    self.PA[ry] = rx
                else:
                    self.PA[ry] += self.PA[rx]
                    aax = self.mult(a, ax)
                    self.rel[rx] = (self.div(ay, aax), self.div(self.minus(by, self.add(b, self.mult(a, bx))), aax))
                    self.PA[rx] = ry
        elif vx is None:
            if self.PA[ry] >= self.PA[rx]:
                self.PA[rx] += self.PA[ry]
                self.rel[ry] = (self.div(self.mult(ax, a), ay), self.div(self.minus(self.add(self.mult(a, bx), b), by), ay))
                self.PA[ry] = rx
                _vx = self.div(self.minus(vy, b), a)
                _vrx = self.div(self.minus(_vx, bx), ax)
                self.value[rx] = _vrx
            else:
                self.PA[ry] += self.PA[rx]
                aax = self.mult(a, ax)
                self.PA[rx] = ry
                self.rel[rx] = (self.div(ay, aax), self.div(self.minus(by, self.add(b, self.mult(a, bx))), aax))
        elif vy is None:
            if self.PA[ry] >= self.PA[rx]:
                self.PA[rx] += self.PA[ry]
                self.PA[ry] = rx
                self.rel[ry] = (self.div(self.mult(ax, a), ay), self.div(self.minus(self.add(self.mult(a, bx), b), by), ay))
            else:
                self.PA[ry] += self.PA[rx]
                aax = self.mult(a, ax)
                self.rel[rx] = (self.div(ay, aax), self.div(self.minus(by, self.add(b, self.mult(a, bx))), aax))
                self.PA[rx] = ry
                _vy = self.add(self.mult(vx, a), b)
                _vry = self.div(self.minus(_vy, by), ay)
                self.value[ry] = _vry
        else:
            if self.add(self.mult(vx, a), b) == vy:
                if rx == ry:
                    # print("Consistent with prior information. Do nothing")
                    pass
                else:
                    # print("Consistent with prior information, but need to connect")
                    if self.PA[ry] >= self.PA[rx]:
                        self.PA[rx] += self.PA[ry]
                        self.rel[ry] = (self.div(self.mult(ax, a), ay), self.div(self.minus(self.add(self.mult(a, bx), b), by), ay))
                        self.PA[ry] = rx
                    else:
                        self.PA[ry] += self.PA[rx]
                        aax = self.mult(a, ax)
                        self.rel[rx] = (self.div(ay, aax), self.div(self.minus(by, self.add(b, self.mult(a, bx))), aax))
                        self.PA[rx] = ry
            else:
                if self.PA[ry] >= self.PA[rx]:
                    self.PA[rx] += self.PA[ry]
                    self.PA[ry] = rx
                    self.value[rx] = self.contradiction_str
                else:
                    self.PA[ry] += self.PA[rx]
                    self.PA[rx] = ry
                    self.value[ry] = self.contradiction_str
                self.contradiction = 1
                return 0
        return 1
                
            
    def size(self, x):
        return -self.PA[self.root(x)]
    def groups(self):
        G = [[] for _ in range(self.n)]
        for i in range(self.n):
            G[self.root(i)].append(i)
        return [g for g in G if g]
    def groups_index(self):
        G = [[] for _ in range(self.n)]
        for i in range(self.n):
            G[self.root(i)[0]].append(i)
        cnt = 0
        GG = []
        I = [-1] * self.n
        for i in range(self.n):
            if G[i]:
                GG.append(G[i])
                I[i] = cnt
                cnt += 1
        return GG, I
    def group_size(self):
        G = [[] for _ in range(self.n)]
        for i in range(self.n):
            G[self.root(i)].append(i)
        return [len(g) for g in G if g]
    def debug(self):
        GG, I = self.groups_index()
        print("GG =", GG)
        print("I =", I)
        print("PA =", self.PA)
        print("rel =", self.rel)

P = 31
from random import randrange, random
if 0:
    # 係数はZで、積閉集合は {1, -1}
    # 2 で割る必要があるため、2倍した値を持っている
    one = 2
    zero = 0
    add = lambda x, y: x + y
    minus = lambda x, y: x - y
    mult = lambda x, y: x * y // 2 if x * y % 2 == 0 else 1 // 0
    div = lambda x, a: x * 2 // a if x * 2 % a == 0 else 1 // 0
    randa = lambda: randrange(-2, 3, 4)
    randx = lambda: randrange(-20, 22, 2)
elif 1:
    # 係数はZで、積閉集合は {1}
    # 通常の Potential UF
    one = 1
    zero = 0
    add = lambda x, y: x + y
    minus = lambda x, y: x - y
    mult = lambda x, y: x * y
    div = lambda x, a: x // a
    randa = lambda: 1
    randx = lambda: randrange(-20, 21)
elif 0:
    # 係数が non-zero float
    one = 1.0
    zero = 0.0
    add = lambda x, y: x + y
    minus = lambda x, y: x - y
    mult = lambda x, y: x * y
    div = lambda x, a: x / a
    randa = lambda: random() * 2 - 1
    randx = lambda: random() * 20 - 10
elif 0:
    # 係数が Z/pZ
    one = 1
    zero = 0
    add = lambda x, y: (x + y) % P
    minus = lambda x, y: (x - y) % P
    mult = lambda x, y: x * y % P
    div = lambda x, a: x * pow(a, P - 2, P) % P
    randa = lambda: randrange(1, P)
    randx = lambda: randrange(P)
elif 0:
    # 係数が Z/2Z で差のみ与えられる（通常の Potential UF）
    one = 1
    zero = 0
    add = lambda x, y: x ^ y
    minus = lambda x, y: x ^ y
    mult = lambda x, y: x & y
    div = lambda x, a: x & a
    randa = lambda: 1
    randx = lambda: randrange(2)

DEBUG = 0
if DEBUG:
    n = 5
    uf = GeneralRelationUnionFind(n, one, zero, add, minus, mult, div, randa, randx)
    uf.check()
    if 0:
        uf.unite(1, 2, 1, 3)
        uf.unite(2, 4, 1, 10)
    # assert uf.unite(1, 2, 2, 3)
    assert uf.unite(3, 4, 2, 10)
    assert uf.unite(2, 3, -2, 2)
    assert uf.unite(2, 3, 2, 4)
    # assert uf.unite(2, 4, 1, 1)
    assert uf.setvalue(4, 16)
    for i in range(5):
        print("Value ", i, "=", uf.getvalue(i))
    print(uf.relation(4, 1))

    uf.debug()

    print("-" * 20)
    uf = IntegerRelationUnionFind(11)
    assert uf.set_sum(1, 2, 3)
    assert uf.set_dif(1, 2, 7)
    assert uf.set_sum(4, 1, 11)

    assert uf.set_sum(6, 9, 3)
    assert uf.set_sum(6, 10, 12)
    print(uf.relation(9, 10))

    for i in range(10):
        print(i, uf.getvalue(i))

    print("-" * 20)

##### ここから #####
if 0:
    # ABC 280-F
    N, M, Q = map(int, input().split())
    uf = PotentialUnionFind(N)
    for _ in range(M):
        a, b, c = map(int, input().split())
        a, b = a-1, b-1
        ret = uf.unite(a, b, c)
    for _ in range(Q):
        x, y = [int(a) - 1 for a in input().split()]
        if uf.same(x, y):
            if uf.guf.value[uf.guf.root(x)[0]] == "!":
                print("inf")
            else:
                print(uf.diff(x, y))
        else:
            print("nan")

# ABC 087-D
N, M = map(int, input().split())
uf = PotentialUnionFind(N)
for _ in range(M):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    ret = uf.unite(l, r, d)
    if not ret:
        print("No")
        break
else:
    print("Yes")

Submission Info

Judge Result