Editorial for Bad Maths

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Track each variable's value relative to a representative using a weighted DSU.

Store for every node $v$ ~v~ a multiplier $r_v$ ~r_v~ meaning "the value of $v$ ~v~ equals $r_v$ ~r_v~ times the value of its parent". Path compression multiplies these weights along the way. When adding $a \times b = c$ ~a \times b = c~:

If $a$ ~a~ and $b$ ~b~ are already in the same component, check whether the implied product matches $c$ ~c~.
Otherwise link the two roots and set the new edge weight so the equation holds.

Inconsistent equations are rejected (No) and ignored afterwards. The whole pass is nearly linear in $n$ ~n~.

Solution (Python)

class DisjointSet():

    def __init__(self) -> None:
        self.parent = dict[str,str]()
        self.relative_to_par = dict[str,int]()
        self.size = dict[str,int]()


    def make_set(self, v : str) -> None:
        if v not in self.parent:
            self.parent[v] = v
            self.size[v] = 1
            self.relative_to_par[v] = 1

    def find_set(self,v : str) -> tuple[str,int]:
        """
        Returns: (highest parent, value relative to that parent)
        """

        if (self.parent[v] == v): return (v,1)

        parent,value = self.find_set(self.parent[v])

        self.parent[v] = parent
        self.relative_to_par[v] = value * self.relative_to_par[v]

        return (self.parent[v], self.relative_to_par[v])

    def new_eq(self,v : str, u : str, val : int) -> bool:
        a, uval = self.find_set(v)
        b, vval = self.find_set(u)

        if a == b:
            # Checks if current values are consistent
            return uval * vval == val

        val *= uval * vval

        if (self.size[a] > self.size[b]):
            a,b = b,a

        self.parent[a] = b
        self.relative_to_par[a] = val
        self.size[b] += self.size[a]

        return True

n = int(input())

dsu = DisjointSet()

for _ in range(n):
    a,b,v = (x for x in input().split())
    v = int(v)

    dsu.make_set(a)
    dsu.make_set(b)

    print("Yes" if dsu.new_eq(a,b,v) else "No")

Comments

There are no comments at the moment.