Submission #1307570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307570		bbeksneckk	Tug of War (BOI15_tug)	Pypy 3	23 / 100	193 ms	59100 KiB

tug

import sys

def m():
    z=sys.stdin.read().split()
    if not z:return
    it=iter(z)
    try:
        n=int(next(it))
        k=int(next(it))
    except StopIteration:return

    g=[[]for _ in range(2*n+1)]
    d=[0]*(2*n+1)
    e=[]
    
    for i in range(2*n):
        u=int(next(it))
        v=int(next(it))+n
        s=int(next(it))
        e.append([u,v,s,0])
        g[u].append(i)
        g[v].append(i)
        d[u]+=1
        d[v]+=1

    q=[i for i in range(1,2*n+1) if d[i]==1]
    h=0
    diff=0

    while h<len(q):
        u=q[h]
        h+=1
        if d[u]==0:continue
        idx=-1
        for x in g[u]:
            if not e[x][3]:
                idx=x
                break
        if idx<0:continue
        
        c=e[idx]
        c[3]=1
        w=c[2]
        if u<=n:diff+=w
        else:diff-=w
        
        v=c[1] if c[0]==u else c[0]
        d[u]-=1
        d[v]-=1
        if d[v]==1:q.append(v)

    p=[]
    for i in range(1,2*n+1):
        if d[i]==0:continue
        if d[i]!=2:
            print("NO")
            return
        curr=i
        val=0
        while d[curr]>0:
            idx=-1
            for x in g[curr]:
                if not e[x][3]:
                    idx=x
                    break
            if idx<0:break
            c=e[idx]
            c[3]=1
            w=c[2]
            if curr<=n:val+=w
            else:val-=w
            nxt=c[1] if c[0]==curr else c[0]
            d[curr]=0
            curr=nxt
        diff+=val
        p.append(abs(val*2))

    b=1
    for x in p:
        b|=(b<<x)
    
    mn=diff-k
    mx=diff+k
    l=max(0,mn)
    
    if l>mx:
        print("NO")
    else:
        chk=(1<<(mx-l+1))-1
        if(b>>l)&chk:print("YES")
        else:print("NO")

if __name__=='__main__':
    m()

Compilation message (stdout)

Compiling 'tug.py'...

=======
  adding: __main__.pyc (deflated 42%)

=======

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29