Submission #1307571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307571		bbeksneckk	Tug of War (BOI15_tug)	Pypy 3	100 / 100	321 ms	121980 KiB

tug

import sys
from collections import Counter

def m():
    z=sys.stdin.read().split()
    if not z:return
    it=iter(z)
    try:
        n=int(next(it))
        k=int(next(it))
    except: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]) # u, v, strength, used
        g[u].append(i)
        g[v].append(i)
        d[u]+=1
        d[v]+=1

    # Topological sort (peeling leaves)
    q=[i for i in range(1,2*n+1) if d[i]==1]
    h=0
    base=0

    while h<len(q):
        u=q[h];h+=1
        if d[u]==0:continue # Already processed
        
        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 # mark edge used
        w=c[2]
        
        # Edge must point TO u (v->u)
        # If u is Left (<=n), v->u is R->L (Team A, +s)
        # If u is Right (>n), v->u is L->R (Team B, -s)
        if u<=n: base+=w
        else: base-=w
        
        v=c[1] if c[0]==u else c[0]
        d[u]-=1
        d[v]-=1
        if d[v]==1:q.append(v)

    deltas=[]
    
    # Process cycles
    for i in range(1,2*n+1):
        if d[i]==0:continue
        if d[i]!=2:
            print("NO") # Impossible structure
            return
            
        curr=i
        val=0
        
        # Traverse cycle
        while d[curr]>0:
            d[curr]=0 # Visit node
            idx=-1
            for x in g[curr]:
                if not e[x][3]:
                    idx=x
                    break
            
            c=e[idx]
            c[3]=1
            w=c[2]
            
            # Orient curr->next
            # If curr Left: L->R (Team B, -s)
            # If curr Right: R->L (Team A, +s)
            if curr<=n: val-=w
            else: val+=w
            
            curr=c[1] if c[0]==curr else c[0]
            
        # We can either keep orientation (val) or flip (-val).
        # We normalize to: start with -abs(val), can add 2*abs(val)
        av=abs(val)
        base-=av
        if av>0: deltas.append(2*av)

    # Knapsack with bitset and count optimization
    cnt=Counter(deltas)
    mask=1
    
    for w,c in cnt.items():
        if w==0:continue
        cur=1
        while c>=cur:
            mask|=(mask<<(w*cur))
            c-=cur
            cur*=2
        if c>0:
            mask|=(mask<<(w*c))
            
    # We need (base + subset_sum) in [-k, k]
    # subset_sum in [-k - base, k - base]
    mn = -k - base
    mx = k - base
    
    if mx < 0:
        print("NO")
        return
        
    start = max(0, mn)
    # Check if any bit set in range [start, mx]
    # (mask >> start) & ((1<<(mx-start+1))-1)
    if start > mx:
        print("NO")
    else:
        chk=(1<<(mx-start+1))-1
        if (mask>>start)&chk:
            print("YES")
        else:
            print("NO")

if __name__=='__main__':
    sys.setrecursionlimit(50000)
    m()

Compilation message (stdout)

Compiling 'tug.py'...

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

=======

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