Problem:


Score : 400 points

Problem Statement

There are N people standing on the x-axis.
Let the coordinate of Person i be x_i.
For every i, x_i is an integer between 0 and 10^9 (inclusive).
It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people.
The i-th piece of information has the form (L_i, R_i, D_i).
This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_{R_i} - x_{L_i} = D_i holds.

It turns out that some of these M pieces of information may be incorrect.
Determine if there exists a set of values (x_1, x_2, ..., x_N) that is consistent with the given pieces of information.

Constraints

1 \leq N \leq 100 000

0 \leq M \leq 200 000

1 \leq L_i, R_i \leq N (1 \leq i \leq M)

0 \leq D_i \leq 10 000 (1 \leq i \leq M)

L_i \neq R_i (1 \leq i \leq M)

If i \neq j, then (L_i, R_i) \neq (L_j, R_j) and (L_i, R_i) \neq (R_j, L_j).

D_i are integers.

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

Output

If there exists a set of values (x_1, x_2, ..., x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

Sample Input 1

3 3
1 2 1
2 3 1
1 3 2

Sample Output 1

Yes

Some possible sets of values (x_1, x_2, x_3) are (0, 1, 2) and (101, 102, 103).

Sample Input 2

3 3
1 2 1
2 3 1
1 3 5

Sample Output 2

No

If the first two pieces of information are correct, x_3 - x_1 = 2 holds, which is contradictory to the last piece of information.

Sample Input 3

4 3
2 1 1
2 3 5
3 4 2

Sample Output 3

Yes

Sample Input 4

10 3
8 7 100
7 9 100
9 8 100

Sample Output 4

No

Sample Input 5

100 0

Sample Output 5

Yes



Sample input:
3 3
1 2 1
2 3 1
1 3 2


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())

RD = []
end = [False] * N

for i in range(N):

    RD.append([])

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q = [endp] 


        while len(Q) > 0:

            q = Q.pop(0)
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []
end = [False] * N

for i in range(N):

    RD.append([])

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q = [endp] 


        while len(Q) > 0:

            q = Q.pop(0)
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    ans = "No"
                    break

            if ans == "No":
                break

        if ans == "No":
            break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []
end = [False] * N

for i in range(N):

    RD.append([])

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q = [endp] 
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)
        end[q] = False

        if cor[q] == "x":
            cor[q] = 0

        for r,d in RD[q]:

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break

    if ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []
end = [False] * N

for i in range(N):

    RD.append([])

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)
        end[q] = False

        if cor[q] == "x":
            cor[q] = 0

        for r,d in RD[q]:

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break

    if ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []
end = [1] * N

for i in range(N):

    RD.append([])

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = 0
    end[R-1] = 0
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp] == 0:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)
        end[q] = 1

        if cor[q] == "x":
            cor[q] = 0

        for r,d in RD[q]:

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break

    if ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []
p = []
rank = []

for i in range(N):

    RD.append([])
    p.append(i)
    rank.append(1)


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp] == 0:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)
        end[q] = 1

        if cor[q] == "x":
            cor[q] = 0

        for r,d in RD[q]:

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break

    if ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp] == 0:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        endnum += 1
        end[q] = 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp] == 0:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break
        endnum += 1
        end[q] = 1

    if ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"

while endnum < N:

    while True:

        if end[endp] == 0:
            Q.append(endp)
            break

        endp += 1

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break
        endnum += 1
        end[q] = 1

    if ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"

while endnum < N:

    while True:

        if end[endp] == 0:
            Q.append(endp)
            break

        endp += 1

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"

        endnum += 1
        end[q] = 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:


N,M = map(int,input().split())

point = ["x"] * N
lis = []
notend = set([])

for i in range(N):

    lis.append([])
    notend = notend | set([i])


for i in range(M):

    L,R,D = map(int,input().split())

    lis[L-1].append([R-1,D])
    lis[R-1].append([L-1,-1 * D])

ans = "Yes"
Q = []

while True:

    if len(notend) > 0:
        Q.append(notend.pop())
    else:
        break

    nmin = 0
    nmax = 0

    while len(Q) > 0:

        q = Q.pop(0)
        if point[q] == "x":
            point[q] = 0

        for rd in lis[q]:

            #ind = bisect.bisect_left(notend,rd[0])

            #print (ind,notend,rd[0])

            if rd[0] in notend:
                notend = notend - set([rd[0]])
                point[rd[0]] = point[q] + rd[1]
                nmin = min(nmin,point[rd[0]])
                nmax = max(nmin,point[rd[0]])
                Q.append(rd[0])

            elif point[rd[0]] != point[q] + rd[1]:
                ans = "No"
                break

        if ans == "No":
            break

    if nmax - nmin > 10 ** 9:
        ans = "No"

    if  ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
input = sys.stdin.readline
INF=float('inf')

def solve():
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]

    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m

    for i in range(m):
        nbr[l[i][0]-1].append([l[i][0]-1,l[i][1]-1,l[i][2],i])
        nbr[l[i][1]-1].append([l[i][1]-1,l[i][0]-1,-l[i][2],i])
    #print(nbr)
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            q=queue.Queue()
            for x in nbr[i]:
                q.put(x)
            while not q.empty():
                eg=q.get()
                used[eg[3]]=True
                if d[eg[1]]==d[eg[0]]+eg[2]:
                    pass
                elif d[eg[1]]==INF:
                    d[eg[1]]=d[eg[0]]+eg[2]
                else:
                    print('No')
                    exit()
                for x in nbr[eg[1]]:
                    if not used[x[3]]:
                        q.put(x)
    #print(d)
    print('Yes')
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
input = sys.stdin.readline
INF=float('inf')
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]

d=[INF]*n
nbr=[[] for _ in range(n)]
used=[False]*m

for i in range(m):
    nbr[l[i][0]-1].append([l[i][0]-1,l[i][1]-1,l[i][2],i])
    nbr[l[i][1]-1].append([l[i][1]-1,l[i][0]-1,-l[i][2],i])
#print(nbr)
for i in range(n):
    if d[i]==INF:
        d[i]=0
        q=queue.Queue()
        for x in nbr[i]:
            q.put(x)
        while not q.empty():
            eg=q.get()
            used[eg[3]]=True
            if d[eg[1]]==d[eg[0]]+eg[2]:
                pass
            elif d[eg[1]]==INF:
                d[eg[1]]=d[eg[0]]+eg[2]
            else:
                print('No')
                exit()
            for x in nbr[eg[1]]:
                if not used[x[3]]:
                    q.put(x)
#print(d)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    INF=float('inf')
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]
    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m
    for x in l:
        x[0]-=1
        x[1]-=1
    #print(l)
    for i in range(m):
        nbr[l[i][0]].append(i)
        nbr[l[i][1]].append(i)
    #print(nbr)
    def sol(i):
        for x in nbr[i]:
            if used[x]:continue
            used[x]=True
            i1=l[x][0]^l[x][1]^i
            dd=d[i]+l[x][2]*(2*(l[x][0]==i)-1)
            if d[i1]==INF:
                d[i1]=dd
            elif d[i1]!=dd:
                print('No')
                exit()
            sol(i1)
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            sol(i)
    #print(d)
    print('Yes')
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    INF=float('inf')
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]
    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m
    for x in l:
        x[0]-=1
        x[1]-=1
    #print(l)
    for i in range(m):
        nbr[l[i][0]].append(i)
        nbr[l[i][1]].append(i)
    #print(nbr)
    def sol(i):
        for x in nbr[i]:
            if used[x]:continue
            used[x]=True
            if l[x][0]==i:
                if d[l[x][1]]==INF:
                    d[l[x][1]]=d[i]+l[x][2]
                elif d[l[x][1]]!=d[i]+l[x][2]:
                    print('No')
                    exit()
                sol(l[x][1])
            else:
                if d[l[x][0]]==INF:
                    d[l[x][0]]=d[i]-l[x][2]
                elif d[l[x][0]]!=d[i]-l[x][2]:
                    print('No')
                    exit()
                sol(l[x][0])
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            sol(i)
    #print(d)
    print('Yes')
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    INF=float('inf')
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]
    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m
    for x in l:
        x[0]-=1
        x[1]-=1
    #print(l)
    for i in range(m):
        nbr[l[i][0]].append(i)
        nbr[l[i][1]].append(i)
    #print(nbr)
    def sol(i):
        if d[i]==INF:
            d[i]=0
        for x in nbr[i]:
            if used[x]:continue
            used[x]=True
            if l[x][0]==i:
                if d[l[x][1]]==INF:
                    d[l[x][1]]=d[i]+l[x][2]
                elif d[l[x][1]]!=d[i]+l[x][2]:
                    print('No')
                    exit()
                sol(l[x][1])
            else:
                if d[l[x][0]]==INF:
                    d[l[x][0]]=d[i]-l[x][2]
                elif d[l[x][0]]!=d[i]-l[x][2]:
                    print('No')
                    exit()
                sol(l[x][0])
    for i in range(n):
        sol(i)
    #print(d)
    print('Yes')
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
INF=float('inf')
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
d=[INF]*n
nbr=[[] for _ in range(n)]
used=[False]*m
for x in l:
    x[0]-=1
    x[1]-=1
#print(l)
for i in range(m):
    nbr[l[i][0]].append(i)
    nbr[l[i][1]].append(i)
#print(nbr)
def sol(i):
    if d[i]==INF:
        d[i]=0
    for x in nbr[i]:
        if used[x]:continue
        used[x]=True
        if l[x][0]==i:
            if d[l[x][1]]==INF:
                d[l[x][1]]=d[i]+l[x][2]
            elif d[l[x][1]]!=d[i]+l[x][2]:
                print('No')
                exit()
            sol(l[x][1])
        else:
            if d[l[x][0]]==INF:
                d[l[x][0]]=d[i]-l[x][2]
            elif d[l[x][0]]!=d[i]-l[x][2]:
                print('No')
                exit()
            sol(l[x][0])
for i in range(n):
    sol(i)
#print(d)
print('Yes')

Submission status: Time Limit Exceeded

Solution code:

N,M = map(int,input().split())

num = [0] * N
far = [0] * N
RD = []
tps = []
p = []

for i in range(N):
    RD.append([])
    p.append(set([i]))

for i in range(M):

    L,R,D = map(int,input().split())

    num[R-1] += 1
    RD[L-1].append([R-1,D])

Q = []

for i in range(N):
    if num[i] == 0:
        Q.append(i)

while len(Q) > 0:

    q = Q.pop(0)
    num[q] -= 1
    tps.append(q)

    for rd in RD[q]:

        r = rd[0]
        num[r] -= 1
        if num[r] == 0:
            Q.append(r)


flag = True
for i in range(N):

    if num[i] > 0:
        flag = False

maxfar = 0
#print (flag)


if flag:

    for i in tps:

        for ra in RD[i]:

            if len(p[ra[0]] & p[i]) > 0 and far[ra[0]] != far[i] + ra[1]:
                flag = False

            p[ra[0]] = p[ra[0]] | p[i]
            far[ra[0]] = max(far[ra[0]],far[i] + ra[1])
            maxfar = max(maxfar,far[ra[0]])

            

#print (far)
if flag and maxfar <= 10 ** 9:
    print ("Yes")
else:
    print ("No")

Submission status: Time Limit Exceeded

Solution code:

import bisect

N,M = map(int,input().split())

point = ["x"] * N
lis = []
notend = []

for i in range(N):

    lis.append([])
    notend.append(i)


for i in range(M):

    L,R,D = map(int,input().split())

    lis[L-1].append([R-1,D])
    lis[R-1].append([L-1,-1 * D])

ans = "Yes"
Q = []

while True:

    if len(notend) > 0:
        Q.append(notend.pop(0))
    else:
        break

    nmin = 0
    nmax = 0

    while len(Q) > 0:

        q = Q.pop(0)
        if point[q] == "x":
            point[q] = 0

        for rd in lis[q]:

            ind = bisect.bisect_left(notend,rd[0])

            #print (ind,notend,rd[0])

            if len(notend) > ind and notend[ind] == rd[0]:
                del notend[ind]
                point[rd[0]] = point[q] + rd[1]
                nmin = min(nmin,point[rd[0]])
                nmax = max(nmin,point[rd[0]])
                Q.append(rd[0])

            elif point[rd[0]] != point[q] + rd[1]:
                ans = "No"
                break

        if ans == "No":
            break

    if nmax - nmin > 10 ** 9:
        ans = "No"

    if  ans == "No":
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():
    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for _ in range(M):
        L, R, D = map(int, input().split())
        graph[L][R] = D
        graph[R][L] = -D

    visited = set()
    for i in range(1, N+1):
        if i not in visited:
            cur = dict()
            cur[i] = 0
            while True:
                temp = dict()
                for j in cur:
                    for k in graph[j]:
                        l = cur[j] + graph[j][k]
                        if k not in cur:
                            temp[k] = l
                        elif k in cur and cur[k] != l:
                            return "No"
                        elif k in temp and temp[k] != l:
                            return "No"
                for k in temp:
                    cur[k] = temp[k]
                if len(temp) == 0:
                    break
    return "Yes"

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = IR(3)
    a -= b
    print(a % c)
    return

#B
def B():
    a, b, c, x, ans = II(), II(), II(), II(), 0
    for i in range(a + 1):
        for j in range(b + 1):
            for k in range(c + 1):
                if i * 500 + j * 100 + k * 50 == x:
                    ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    dp = [[0] * (n + 1) for i in range(2)]
    for i in range(1, n + 1):
        dp[0][i] += dp[0][i - 1] + a[i - 1]
    a = LI()
    for i in range(1, n + 1):
        dp[1][i] = max(dp[0][i], dp[1][i - 1]) + a[i - 1]
    print(dp[1][-1])
    
    return


class Value_UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.differ_weight[x] += self.differ_weight[self.par[x]]
        self.par[x] = r
        return r

    def weight(self, x):
        self.root(x)
        return self.differ_weight[x]

    def unit(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        self.par[y] = x
        self.differ_weight[y] = w
        return True

    def differ(self, x, y):
        return self.weight(y) - self.weight(x)
#D
def D():
    n, m = LI()
    u = Value_UnionFind(n)
    for _ in range(m):
        l, r, d = LI_()
        if not u.unit(l, r, d + 1):
            if u.differ(l, r) == d + 1:
                continue
            else:
                print("No")
                return
    print("Yes")


    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N+1)]
x = [0] * (N+1)
visited = [False] * (N+1)

for i in range(M):
    L, R, D = map(int, input().split())
    G[L].append((R, D))
    G[R].append((L, -D))

for i in range(1, N+1):
    if not visited[i]:
        q = G[i]
        visited[i] = True
        while q:
            u, d = q.pop(0)
            if not visited[u]:
                x[u] = d
                visited[u] = True
                for v, d_ in G[u]:
                    q.append((v, d+d_))
            
            else:
                if x[u] != d:
                    print('No')
                    exit()
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
"""
https://atcoder.jp/contests/abc087/tasks/arc090_b

xR-xL = D
Mこの情報が正しいかどうかの判定
グループを作って、グループ内の拘束条件があっているか確認
重み付きunionfindを使う
https://qiita.com/drken/items/cce6fc5c579051e64fab
http://at274.hatenablog.com/entry/2018/02/03/140504


5 5
1 2 2
2 3 3
4 5 4
2 5 10
3 4 3
"""

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def calc_weight(self, x):
        self.find(x) #圧縮
        return self.weight[x]

    def calc_diff(self, x, y):
        return self.calc_weight(y) - self.calc_weight(x)

    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] = - w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0


    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)


N,M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    l,r,d = map(int, input().split())
    # 初めて出てくる奴らは数直線形成に使う
    if not uf.judge(l, r):
        uf.weighted_union(l, r, d)
    # 二回目のやつらは後で拘束条件に使う
    else:
        # print(d,uf.calc_diff(r,l))
        if d == uf.calc_diff(r,l):
            continue
        else:
            print("No")
            exit()
print("Yes")
# for i in uf.parent.keys():
#     uf.find(i)
#     print("index:{} rank:{}, parent:{}, weight:{}".format(i,uf.rank[i],uf.parent[i],uf.weight[i]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges[l].append((r, d))
    edges[r].append((l, -d))


coord = [None for i in range(n)]
def dfs(v):
    possible = True
    for u, d in edges[v]:
        if not possible:
            break
        if coord[u]:
            if coord[u] != coord[v] + d:
                return False
        else:
            # not visited yet
            coord[u] = coord[v] + d
            possible = possible and dfs(u)

    return possible

ans = True
for i in range(n):
    if coord[i] or not ans:
        continue
    coord[i] = 0
    ans = ans and dfs(i)


if ans:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges[l].append((r, d))
    edges[r].append((l, -d))


coord = [None for i in range(n)]
def dfs(v):
    possible = True
    for u, d in edges[v]:
        if not possible:
            break
        if coord[u]:
            if coord[u] != coord[v] + d:
                return False
        else:
            # not visited yet
            coord[u] = coord[v] + d
            possible = possible and dfs(u)

    return possible

ans = True
for i in range(n):
    if coord[i]:
        continue
    coord[i] = 0
    ans = ans and dfs(i)

if ans:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    edges[l].append((r, d))
    edges[r].append((l, -d))


coord = [None for i in range(n)]
def dfs(v):
    possible = True
    for u, d in edges[v]:
        if coord[u]:
            if coord[u] != coord[v] + d:
                return False
        else:
            # not visited yet
            coord[u] = coord[v] + d
            possible = possible and dfs(u)

    return possible

ans = True
for i in range(n):
    if coord[i]:
        continue
    coord[i] = 0
    ans = ans and dfs(i)

if ans:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
LRD = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for L,R,D in LRD:
    E[L-1][R-1] = D
    E[R-1][L-1] = -D

V = [-1]*N
breakFlg = False
for i in range(N):
    if V[i]!=-1:continue
    V[0] = 0
    q = [i]
    while q:
        j = q.pop()
        v = V[j]
        for k,d in E[j].items():
            if V[k] == -1:
                V[k] = v+d
                q.append(k)
ans = True
for l,e in enumerate(E):
    for r,d in e.items():
        ans = ans and V[r]-V[l]==d
    if not ans:break
print("Yes" if ans else "No")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
LRD = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for L,R,D in LRD:
    E[L-1][R-1] = D
    E[R-1][L-1] = -D

V = [-1]*N
breakFlg = False
for i in range(N):
    if V[i]!=-1:continue
    V[0] = 0
    q = [i]
    while q:
        j = q.pop()
        v = V[j]
        for k,d in E[j].items():
            if V[k] == -1:
                V[k] = v+d
                q.append(k)
            else:
                breakFlg = V[k] != v+d
            if breakFlg:break
        if breakFlg:break
    if breakFlg:break
print("No" if breakFlg else "Yes")