USACO Revegetate - Version 1

USACO 2019 February Contest, Silver¶

Problem 3. The Great Revegetation¶

http://usaco.org/index.php?page=viewproblem2&cpid=920

In [1]:

fin = open ('2.in', 'r')
fout = open ('revegetate.out', 'w')
N,M  = map(int, fin.readline().split())
print("N M",N,M)

N M 4000 5383

In [2]:

# cut-and-paste Union-Find code
PARENT = [i for i in range(N+1)]
def find_with_path_compression(x):
    if x!=PARENT[x]:
        PARENT[x]=find_with_path_compression(PARENT[x])
    return PARENT[x]

def union(x,y):
    a = find_with_path_compression(x)
    b = find_with_path_compression(y)
    PARENT[a]=b
    return

In [3]:

for i in range(M):  
    i,j,k = fin.readline().split()
    p1=int(j)
    p2=int(k)
    union(p1,p2)

In [4]:

countset = set()
for i in range(1,N+1):
    countset.add(find_with_path_compression(i))
print("connected components",len(countset))

connected components 289

In [5]:

# every connected component means number of ways x2
# so the answer is a power of 2, and is written in binary
ans = '1'
for i in range(len(countset)):
    ans += '0'

print("ans",ans)
fout.write(str(ans)+"\n")
fout.close()

ans 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

This code fails on data set 11.¶

It does not check for conflicting dietary restrictions that would mean NO SOLUTION.