Problem:


Problem D: Room of Time and Spirit

Problem

　20XX年、とある科学者がバイオテクノロジーによって強力な人造人間を開発してしまった。この人造人間はコンピュータにより、戦闘の達人たちの細胞を組み合わせて作られているため非常に強力である。

　このままでは地球は人造人間に支配されてしまうので、 N 人の戦士たちは人造人間と戦うことにした。しかし今の戦士たちでは到底人造人間に敵わないため、修行をしなければならない。また、N 人の戦士たちはそれぞれ 1 ~ N の番号が付いている。

　この時代、天空都市AIZUには SRLU室と呼ばれる修行のための特殊な部屋が存在した。この部屋での1年は外界の時間の1日と同じであるため、短期間で戦闘力を大幅に上昇することが出来る。同時に部屋に入れる人数の上限は2人である。また、その2人が部屋に入った時、それぞれ戦闘力が上昇する。

　戦士たちは残された時間でどのように部屋に入るか検討するため、あなたに以下のクエリを処理するプログラムの作成を依頼した。

　与えられるクエリは以下の通りである。

　また以下の説明で出てくる A, B はそれぞれ戦士の番号を表す。A と B が等しい事は無い。

	
IN A B C

　A と B が部屋に入り、それぞれ C だけ戦闘力が上昇する。この時、(部屋に入る直前の B の戦闘力) - (部屋に入る直前の A の戦闘力) = C が成り立つ。また、この時 B の戦闘力は A の戦闘力より高い事が保証される。

COMPARE A B

　A と B の戦闘力の差 (現在の B の戦闘力) - (現在の A の戦闘力)を出力する。もしその差が特定出来なければ、WARNING と出力せよ。

Input

N Q
query1
.
.
.
queryQ

最初に戦士の人数 N , クエリの数 Q が与えられる。

次に Q 回だけクエリが与えられる。

Constraints

入力は以下の条件を満たす。

2 ≤ N ≤ 100000

1 ≤ Q ≤ 100000

1 ≤ A, B ≤ N

1 ≤ C ≤ 5000

Output

上記のように与えられたクエリを順番に処理していき、 COMPAREの入力が与えられた際に出力を行う。

Sample Input1

3 5
COMPARE 1 2
IN 1 2 5
IN 2 3 3
COMPARE 2 3
COMPARE 1 3

Sample Output1

WARNING
3
11

Sample Input2

4 3
IN 1 4 10
IN 2 3 20
COMPARE 1 2

Sample Output2

WARNING

Sample Input3

3 4
IN 2 1 2
IN 3 1 2
COMPARE 1 3
COMPARE 2 3

Sample Output3

-2
2

Sample Input4

10 4
IN 10 8 2328
IN 8 4 3765
IN 3 8 574
COMPARE 4 8

Sample Output4

-3191

Sample Input5

3 5
IN 1 2 5
IN 1 2 5
IN 2 3 10
COMPARE 1 2
COMPARE 2 3

Sample Output5

15
10



Sample input:
3 5
COMPARE 1 2
IN 1 2 5
IN 2 3 3
COMPARE 2 3
COMPARE 1 3


Sample output:
WARNING
3
11

Submission status: Accepted

Solution code:
# AOJ 1519: Room of Time and Spirit
# Python3 2018.7.13 bal4u

# Weighted UNION-FIND library
class WeightedUnionSet:
	def __init__(self, nmax):
		self.ws = [0]*nmax
		self.par = [-1]*nmax
		self.power = [0]*nmax
	def find(self, x):
		if self.par[x] < 0: return x
		p = self.find(self.par[x])
		self.ws[x] += self.ws[self.par[x]]
		self.par[x] = p
		return p
	def weight(self, x):
		self.find(x)
		return self.ws[x]
	def connected(self, x, y): return self.find(x) == self.find(y)
	def unite(self, x, y, w):
		w += self.power[x]+self.weight(x)
		w -= self.power[y]+self.weight(y)
		x, y = self.find(x), self.find(y)
		if x == y: return 0
		if self.par[y] < self.par[x]: x, y, w = y, x, -w
		self.par[x] += self.par[y]
		self.par[y] = x
		self.ws[y] = w
		return 1
	def diff(self, x, y):
		if self.find(x) != self.find(y): return [0, None]
		return [1, self.ws[x]-self.ws[y]]
# Weighted UNION-FIND library

N, Q = map(int, input().split())
u = WeightedUnionSet(N+1)
for i in range(Q):
	q = input().split()
	if q[0] == "IN":
		a, b, c = int(q[1]), int(q[2]), int(q[3])
		u.power[a] += c
		u.power[b] += c
		u.unite(a, b, c)
	else:
		a, b = int(q[1]), int(q[2])
		if u.find(a) != u.find(b): print("WARNING")
		else: print((u.power[b]+u.ws[b])-(u.power[a]+u.ws[a]))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)
        self.added = [0]*(n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        self.added[x] += w
        self.added[y] += w
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            #self.weight[rx] = w - self.weight[x] + self.weight[y]
            self.weight[rx] = w - self.diff(x, y)
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            #self.weight[ry] = -w - self.weight[y] + self.weight[x]
            self.weight[ry] = -w + self.diff(x, y)
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]+self.added[x]-self.added[y]

    def added_diff(self, x, y):
        return self.diff(x, y)


def dealIn(l):
    a, b, c = l
    Un.union(b, a, c)


def compare(l):
    a, b = l
    if Un.same(a, b):
        diff = Un.added_diff(b, a)
        return diff
    else:
        return "WARNING"


N, Q = map(int, input().split())
Un = WeightedUnionFind(N+1)
ans = []
for _ in range(Q):
    s, *l = input().split()
    if s == "IN":
        dealIn(list(map(int, l)))
    else:
        ret = compare(list(map(int, l)))
        ans.append(ret)
if ans:
    print("\n".join(map(str, ans)))

Submission status: WA: Presentation Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)
        self.added = [0]*(n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        self.added[x] += w
        self.added[y] += w
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            #self.weight[rx] = w - self.weight[x] + self.weight[y]
            self.weight[rx] = w - self.diff(x, y)
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            #self.weight[ry] = -w - self.weight[y] + self.weight[x]
            self.weight[ry] = -w + self.diff(x, y)
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]+self.added[x]-self.added[y]

    def added_diff(self, x, y):
        return self.diff(x, y)


def dealIn(l):
    a, b, c = l
    Un.union(b, a, c)


def compare(l):
    a, b = l
    if Un.same(a, b):
        diff = Un.added_diff(b, a)
        return diff
    else:
        return "WARNING"


N, Q = map(int, input().split())
Un = WeightedUnionFind(N+1)
ans = []
for _ in range(Q):
    s, *l = input().split()
    if s == "IN":
        dealIn(list(map(int, l)))
    else:
        ret = compare(list(map(int, l)))
        ans.append(ret)
print("\n".join(map(str, ans)))