**Task Score**

**Correctness**

**Performance**

There is an N **×** N square mesh-shaped grid of wires, as shown in a figure below. Nodes of the grid are at points (X, Y), where X and Y are integers from 0 to N−1. An electric current flows through the grid, between the nodes at (0, 0) and (N−1, N−1).

Initially, all the wires conduct the current, but the wires burn out at a rate of one per second. The burnouts are described by three arrays of integers, A, B and C, each of size M. For each moment T (0 ≤ T < M), in the T-th second the wire between nodes (A[T], B[T]) and:

- (A[T], B[T] + 1), if C[T] = 0 or
- (A[T] + 1, B[T]), if C[T] = 1

burns out. You can assume that the arrays describe existing wires, and that no wire burns out more than once. Your task is to determine when the current stops flowing between the nodes at (0,0) and (N−1,N−1).

Write a function:

def solution(N, A, B, C)

that, given integer N and arrays A, B and C, returns the number of seconds after which the current stops flowing between the nodes at (0, 0) and (N−1, N−1). If the current keeps flowing even after all M wires burn out, the function should return −1.

For example, given N = 4, M = 9 and the following arrays:

`A[0] = 0 B [0] = 0 C[0] = 0 A[1] = 1 B [1] = 1 C[1] = 1 A[2] = 1 B [2] = 1 C[2] = 0 A[3] = 2 B [3] = 1 C[3] = 0 A[4] = 3 B [4] = 2 C[4] = 0 A[5] = 2 B [5] = 2 C[5] = 1 A[6] = 1 B [6] = 3 C[6] = 1 A[7] = 0 B [7] = 1 C[7] = 0 A[8] = 0 B [8] = 0 C[8] = 1`

your function should return 8, because just after the eighth wire burns out, there is no connection between the nodes at (0, 0) and (N−1, N−1). This situation is shown in the following figure:

Given N = 4, M = 1 and the following arrays:

`A[0] = 0 B [0] = 0 C[0] = 0`

your function should return −1, because burning out a single wire cannot break the connection between the nodes at (0, 0) and (N−1, N−1).

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [1..400];
- M is an integer within the range [0..
2*N*(N-1)];- each element of arrays A and B is an integer within the range [0..
N-1];- each element of array C is an integer that can have one of the following values: 0, 1.

*not defined yet*

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Invalid result type, int expected, <type 'NoneType'> found.

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Invalid result type, int expected, <type 'NoneType'> found.

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

**WRONG ANSWER**, got 0 expected -1

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = zip(A,B,C)
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Invalid result type, int expected, <type 'NoneType'> found.

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Invalid result type, int expected, <type 'NoneType'> found.

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set(zip(A,B))
print burnouts
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

set([(0, 1), (3, 2), (1, 3), (2, 1), (0, 0), (2, 2), (1, 1)]) Invalid result type, int expected, <type 'NoneType'> found.

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

set([(0, 0)]) Invalid result type, int expected, <type 'NoneType'> found.

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] = 0:
burnouts.add((A[idx], B[idx+1]))
else:
burnouts.add((A[idx], B[idx+1]))
print burnouts
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 70 if C[idx] = 0: ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 70 if C[idx] = 0: ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx+1]))
else:
burnouts.add((A[idx+1], B[idx]))
print burnouts
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 180, in <module> result = solution ( N, A, B, C ) File "user.py", line 73, in solution burnouts.add((A[idx+1], B[idx])) IndexError: list index out of range

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 180, in <module> result = solution ( N, A, B, C ) File "user.py", line 71, in solution burnouts.add((A[idx], B[idx+1])) IndexError: list index out of range

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
print burnouts
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

set([(0, 1), (1, 2), (3, 2), (3, 3), (2, 1), (2, 3), (2, 2), (1, 0), (0, 2)]) Invalid result type, int expected, <type 'NoneType'> found.

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

set([(0, 1)]) Invalid result type, int expected, <type 'NoneType'> found.

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = [0] * N * N + 2
print grid
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 182, in <module> result = solution ( N, A, B, C ) File "user.py", line 75, in solution grid = [0] * N * N + 2 TypeError: can only concatenate list (not "int") to list

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 182, in <module> result = solution ( N, A, B, C ) File "user.py", line 75, in solution grid = [0] * N * N + 2 TypeError: can only concatenate list (not "int") to list

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = [0] * (N * N + 2)
print grid
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Invalid result type, int expected, <type 'NoneType'> found.

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Invalid result type, int expected, <type 'NoneType'> found.

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
print grid
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n'] Invalid result type, int expected, <type 'NoneType'> found.

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n'] Invalid result type, int expected, <type 'NoneType'> found.

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
uf.union((grid[0], grid[1])
print grid
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 79 print grid ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 79 print grid ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
uf.union((grid[0], grid[1]))
print grid
return
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n'] Invalid result type, int expected, <type 'NoneType'> found.

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
uf.union((grid[0], grid[1]))
print grid
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
print grid
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
print uf[grid[0]]
print grid
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

n ['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

n ['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
print uf[grid[0]]
print grid
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

0 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

0 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A && self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 71 return self.A == other.A && self.B == other.B ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 71 return self.A == other.A && self.B == other.B ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 92 return 0 ^ IndentationError: expected an indented block

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 92 return 0 ^ IndentationError: expected an indented block

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 92 return 0 ^ IndentationError: expected an indented block

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 92 return 0 ^ IndentationError: expected an indented block

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 195, in <module> result = solution ( N, A, B, C ) File "user.py", line 81, in solution burnouts.add(Wrapper(A[idx], B[idx], C[idx])) TypeError: unhashable instance

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 195, in <module> result = solution ( N, A, B, C ) File "user.py", line 81, in solution burnouts.add(Wrapper(A[idx], B[idx], C[idx])) TypeError: unhashable instance

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash(tuple(self))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 198, in <module> result = solution ( N, A, B, C ) File "user.py", line 84, in solution burnouts.add(Wrapper(A[idx], B[idx], C[idx])) File "user.py", line 74, in __hash__ return hash(tuple(self)) TypeError: iteration over non-sequence

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 198, in <module> result = solution ( N, A, B, C ) File "user.py", line 84, in solution burnouts.add(Wrapper(A[idx], B[idx], C[idx])) File "user.py", line 74, in __hash__ return hash(tuple(self)) TypeError: iteration over non-sequence

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash(tuple(self.A, self.B))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 198, in <module> result = solution ( N, A, B, C ) File "user.py", line 84, in solution burnouts.add(Wrapper(A[idx], B[idx], C[idx])) File "user.py", line 74, in __hash__ return hash(tuple(self.A, self.B)) TypeError: tuple() takes at most 1 argument (2 given)

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 198, in <module> result = solution ( N, A, B, C ) File "user.py", line 84, in solution burnouts.add(Wrapper(A[idx], B[idx], C[idx])) File "user.py", line 74, in __hash__ return hash(tuple(self.A, self.B)) TypeError: tuple() takes at most 1 argument (2 given)

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

**WRONG ANSWER**, got 0 expected -1

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404e094c>, <__main__.Wrapper instance at 0x404e092c>, <__main__.Wrapper instance at 0x404e08cc>, <__main__.Wrapper instance at 0x404e08ec>, <__main__.Wrapper instance at 0x404e090c>])

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404e08cc>])

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def __str__(self):
return "Wrapper:", self.A, self.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df9ec>, <__main__.Wrapper instance at 0x404df9cc>, <__main__.Wrapper instance at 0x404df96c>, <__main__.Wrapper instance at 0x404df98c>, <__main__.Wrapper instance at 0x404df9ac>])

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df96c>])

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def __str__(self):
return "Wrapper:", self.A, self.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df9ec>, <__main__.Wrapper instance at 0x404df9cc>, <__main__.Wrapper instance at 0x404df96c>, <__main__.Wrapper instance at 0x404df98c>, <__main__.Wrapper instance at 0x404df9ac>])

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df96c>])

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df9cc>, <__main__.Wrapper instance at 0x404df9ac>, <__main__.Wrapper instance at 0x404df94c>, <__main__.Wrapper instance at 0x404df96c>, <__main__.Wrapper instance at 0x404df98c>])

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df94c>])

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df98c>, <__main__.Wrapper instance at 0x404df94c>, <__main__.Wrapper instance at 0x404df9ac>, <__main__.Wrapper instance at 0x404df92c>, <__main__.Wrapper instance at 0x404df96c>])

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

set([<__main__.Wrapper instance at 0x404df92c>])

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
w = Wrapper(A[idx], B[idx], C[idx])
print w
burnouts.add(w)
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 0, b is 0 Wrapper: a is 1, b is 1 Wrapper: a is 2, b is 1 Wrapper: a is 3, b is 2 Wrapper: a is 0, b is 1 set([<__main__.Wrapper instance at 0x404e098c>, <__main__.Wrapper instance at 0x404e094c>, <__main__.Wrapper instance at 0x404e09ac>, <__main__.Wrapper instance at 0x404e092c>, <__main__.Wrapper instance at 0x404e096c>])

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 0, b is 0 set([<__main__.Wrapper instance at 0x404e092c>])

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 3, b is 2 Wrapper: a is 1, b is 1 Wrapper: a is 0, b is 1 Wrapper: a is 0, b is 0 Wrapper: a is 2, b is 1

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 0, b is 0

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 3, b is 2, c is 0 Wrapper: a is 1, b is 1, c is 0 Wrapper: a is 0, b is 1, c is 0 Wrapper: a is 0, b is 0, c is 0 Wrapper: a is 2, b is 1, c is 0

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 0, b is 0, c is 0

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
print "inserting", A[idx], B[idx], C[idx]
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

inserting 0 0 0 inserting 1 1 0 inserting 2 1 0 inserting 3 2 0 inserting 0 1 0 Wrapper: a is 3, b is 2, c is 0 Wrapper: a is 1, b is 1, c is 0 Wrapper: a is 0, b is 1, c is 0 Wrapper: a is 0, b is 0, c is 0 Wrapper: a is 2, b is 1, c is 0

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

inserting 0 0 0 Wrapper: a is 0, b is 0, c is 0

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 3, b is 2, c is 0 Wrapper: a is 1, b is 1, c is 0 Wrapper: a is 2, b is 1, c is 0 Wrapper: a is 2, b is 2, c is 1 Wrapper: a is 0, b is 0, c is 1 Wrapper: a is 1, b is 3, c is 1 Wrapper: a is 0, b is 0, c is 0 Wrapper: a is 1, b is 1, c is 1 Wrapper: a is 0, b is 1, c is 0

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

Wrapper: a is 0, b is 0, c is 0

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != N-1
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 95 if (left_right, top_down, 0) not in burnouts and top_down != N-1 ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 95 if (left_right, top_down, 0) not in burnouts and top_down != N-1 ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != (N-1)
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 95 if (left_right, top_down, 0) not in burnouts and top_down != (N-1) ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 95 if (left_right, top_down, 0) not in burnouts and top_down != (N-1) ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != N
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 95 if (left_right, top_down, 0) not in burnouts and top_down != N ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 95 if (left_right, top_down, 0) not in burnouts and top_down != N ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != N-1 :
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and (left_right, top_down, 0) not in burnouts :
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and (left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 201, in <module> result = solution ( N, A, B, C ) File "user.py", line 95, in solution if top_down != N-1 and (left_right, top_down, 0) not in burnouts: File "user.py", line 71, in __eq__ return self.A == other.A and self.B == other.B and self.C == other.C AttributeError: 'tuple' object has no attribute 'A'

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 201, in <module> result = solution ( N, A, B, C ) File "user.py", line 95, in solution if top_down != N-1 and (left_right, top_down, 0) not in burnouts: File "user.py", line 71, in __eq__ return self.A == other.A and self.B == other.B and self.C == other.C AttributeError: 'tuple' object has no attribute 'A'

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

**WRONG ANSWER**, got 0 expected -1

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

**WRONG ANSWER**, got 0 expected -1

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[0]
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 100 if uf[0] ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 100 if uf[0] ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

**WRONG ANSWER**, got 0 expected -1

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

0 2 down not in list 1 0 down not in list 1 2 down not in list 2 0 down not in list 2 2 down not in list 3 0 down not in list 3 1 down not in list

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

0 1 down not in list 0 2 down not in list 1 0 down not in list 1 1 down not in list 1 2 down not in list 2 0 down not in list 2 1 down not in list 2 2 down not in list 3 0 down not in list 3 1 down not in list 3 2 down not in list

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

0 1 right not in list 0 2 down not in list 0 2 right not in list 0 3 right not in list 1 0 down not in list 1 0 right not in list 1 2 down not in list 1 2 right not in list 2 0 down not in list 2 0 right not in list 2 1 right not in list 2 2 down not in list 2 3 right not in list 3 0 down not in list 3 1 down not in list

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

0 0 right not in list 0 1 down not in list 0 1 right not in list 0 2 down not in list 0 2 right not in list 0 3 right not in list 1 0 down not in list 1 0 right not in list 1 1 down not in list 1 1 right not in list 1 2 down not in list 1 2 right not in list 1 3 right not in list 2 0 down not in list 2 0 right not in list 2 1 down not in list 2 1 right not in list 2 2 down not in list 2 2 right not in list 2 3 right not in list 3 0 down not in list 3 1 down not in list 3 2 down not in list

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid_size]
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

16

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

16

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid_size], uf[grid_size+1]
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

16 17

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

16 17

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print grid[grid_size-1], uf[grid_size], uf[grid_size+1]
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

15 16 17

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

15 16 17

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

**WRONG ANSWER**, got 0 expected -1

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[grid_size]], uf[grid[grid_size+1]]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

16 17

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

16 17

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

16 17 16 17

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

16 17 16 17

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

0 16 17 16 17

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

8 16 17 16 17

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[0], uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

0 16 17 0 16 17

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

8 16 17 8 16 17

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
print uf[grid[0]], uf[grid[grid_size]]
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[0], uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

0 16 0 16 17 0 16 17

**WRONG ANSWER**, got 0 expected -1

WARNING: producing output may seriously slow down your code!stdout:

0 16 8 16 17 8 16 17

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[0], uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

16 16 12 16 16 12

**OK**

WARNING: producing output may seriously slow down your code!stdout:

8 8 8 8 8 8

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
```

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 107 return 0 ^ IndentationError: expected an indented block

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 107 return 0 ^ IndentationError: expected an indented block

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
print idx
return 0
```

**Example tests**

**WRONG ANSWER**, got 0 expected 8

WARNING: producing output may seriously slow down your code!stdout:

8 7 6 5 4 3 2 1 0

**OK**

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 107 uf.union(grid[A[idx]*N+B[idx], grid[(A[idx]+1)*N+B[idx]]) ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 107 uf.union(grid[A[idx]*N+B[idx], grid[(A[idx]+1)*N+B[idx]]) ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
```

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
```

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
```

[4, [0], [0], [0]]

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
```

[4, [0, 0], [0, 0], [0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 0], [0, 0], [0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 1:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 1:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 1:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if Wrapper(top_down, left_right, 0) not in burnouts:
assert top_down != N-1
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 216, in <module> result = solution ( N, A, B, C ) File "user.py", line 96, in solution assert top_down != N-1 AssertionError

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 216, in <module> result = solution ( N, A, B, C ) File "user.py", line 96, in solution assert top_down != N-1 AssertionError

**User tests**

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 216, in <module> result = solution ( N, A, B, C ) File "user.py", line 96, in solution assert top_down != N-1 AssertionError

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
print top_down, left_right, " to top", did not burn out
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
print top_down, left_right, " to right", did not burn out
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Example tests**

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 96 print top_down, left_right, " to top", did not burn out ^ SyntaxError: invalid syntax

example from the problem statement

**RUNTIME ERROR**

tested program terminated unexpectedly

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 96 print top_down, left_right, " to top", did not burn out ^ SyntaxError: invalid syntax

**User tests**

**RUNTIME ERROR**, tested program terminated unexpectedly

File "user.py", line 96 print top_down, left_right, " to top", did not burn out ^ SyntaxError: invalid syntax

**Failed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
print top_down, left_right, " to top did not burn out"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
print top_down, left_right, " to right did not burn out"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Example tests**

**WRONG ANSWER**, got 9 expected 8

WARNING: producing output may seriously slow down your code!stdout:

1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to right did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out

**OK**

WARNING: producing output may seriously slow down your code!stdout:

0 0 to right did not burn out 1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to top did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out

**User tests**

**OK**

function result: 3

WARNING: producing output may seriously slow down your code!stdout:

1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
print top_down, left_right, " to top did not burn out"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
print top_down, left_right, " to right did not burn out"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Example tests**

**OK**

WARNING: producing output may seriously slow down your code!stdout:

1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out

**OK**

WARNING: producing output may seriously slow down your code!stdout:

0 0 to right did not burn out 1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to top did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out

**User tests**

**OK**

function result: 3

WARNING: producing output may seriously slow down your code!stdout:

1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**Passed**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]

**100**

```
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
```

The solution obtained perfect score.

**O(N**2*log(N)) or O(N**2*log(log(N)))**

**Correctness tests**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**

**Performance tests**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**