Tasks Details
hard
1.
OddNetwork
Given a tree graph, find the number of pairs of vertices whose distance is odd.
Task Score
100%
Correctness
100%
Performance
100%
You analyze the performance of a computer network. The network comprises nodes connected by peer-to-peer links. There are N links and N + 1 nodes. All pairs of nodes are (directly or indirectly) connected by links, and links don't form cycles. In other words, the network has a tree topology.
Your analysis shows that communication between two nodes performs much better if the number of links on the (shortest) route between the nodes is odd. Of course, the communication is fastest when the two nodes are connected by a direct link. But, amazingly, if the nodes communicate via 3, 5, 7, etc. links, communication is much faster than if the number of links to pass is even.
Now you wonder how this influences the overall network performance. There are N * (N + 1) / 2 different pairs of nodes. You need to compute how many of them are pairs of nodes connected via an odd number of links.
Nodes are numbered from 0 to N. Links are described by two arrays of integers, A and B, each containing N integers. For each 0 ≤ I < N, there is a link between nodes A[I] and B[I].
Write a function:
def solution(A, B)
that, given two arrays, A and B, consisting of N integers and describing the links, computes the number of pairs of nodes X and Y, such that 0 ≤ X < Y ≤ N, and X and Y are connected via an odd number of links.
For example, given N = 6 and the following arrays:
A[0] = 0 B[0] = 3 A[1] = 3 B[1] = 1 A[2] = 4 B[2] = 3 A[3] = 2 B[3] = 3 A[4] = 6 B[4] = 3 A[5] = 3 B[5] = 5
the function should return 6, since:
- there are six pairs of nodes connected by direct links, and
- all other pairs of nodes are connected via two links.
Given N = 5 and the following arrays:
A[0] = 0 B[0] = 1 A[1] = 4 B[1] = 3 A[2] = 2 B[2] = 1 A[3] = 2 B[3] = 3 A[4] = 4 B[4] = 5
the function should return 9, since:
- there are five pairs of nodes connected by direct links,
- there are three pairs of nodes connected via three links, and
- there is one pair of nodes connected via five links.
Given N = 7 and the following arrays:
A[0] = 0 B[0] = 3 A[1] = 4 B[1] = 5 A[2] = 4 B[2] = 1 A[3] = 2 B[3] = 3 A[4] = 7 B[4] = 4 A[5] = 6 B[5] = 3 A[6] = 3 B[6] = 4
the function should return 16, since:
- there are seven pairs of nodes connected by direct links, and
- there are nine pairs of nodes connected via three links.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..90,000];
- each element of arrays A and B is an integer within the range [0..N];
- the network has a tree topology;
- any pair of nodes is connected via no more than 1000 links.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 9 minutes
Notes
not defined yet
Code: 15:25:09 UTC,
java,
autosave
Code: 15:25:09 UTC,
java,
autosave
Code: 15:25:14 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built = build_graph(A, B, num_nodes)
if star(graph_built, num_nodes):
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Analysis
Code: 15:25:23 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built = build_graph(A, B, num_nodes)
if star(graph_built, num_nodes):
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:25:41 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built = build_graph(A, B, num_nodes)
if star(graph_built, num_nodes):
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:25:52 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if star(graph_built, num_nodes):
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:26:03 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:26:17 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:26:34 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:26:50 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:27:06 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_nodes[A[i]] =
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:27:27 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
if
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:27:52 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = True
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
if IsStar:
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
if
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:28:05 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = True
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
if IsStar:
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:28:18 UTC,
py,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = True
Node_High = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
if IsStar:
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:28:48 UTC,
py,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = True
Node_High = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
if IsStar:
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
if graph_nodes[A[i]] > 1:
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:29:19 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = True
Node_High = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
if IsStar:
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
if graph_nodes[A[i]] > 1:
if Node_High == False:
Node_High = True
else:
IsStar = False
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:29:30 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = True
Node_High = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
if IsStar:
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
if graph_nodes[A[i]] > 1:
if Node_High == False:
Node_High = True
else:
IsStar = False
if graph_nodes[B[i]] > 1:
if Node_High == False:
Node_High = True
else:
IsStar = False
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:30:01 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = True
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:30:12 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_nodes[A[i]] += 1
graph_nodes[B[i]] += 1
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:30:40 UTC,
py,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [elem ]
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:31:40 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [elem ]
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:31:54 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if ]
flatten_matrix = [val for sublist in matrix for val in sublist]
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:32:17 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) > 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:32:18 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) > 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Analysis
expand all
Example tests
1.
0.040 s
OK
1.
0.040 s
WRONG ANSWER,
got 5 expected 9
1.
0.040 s
WRONG ANSWER,
got 7 expected 16
Code: 15:32:43 UTC,
py,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) > 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
pri
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:32:53 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) > 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
print("Es estrella")
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Analysis
expand all
Example tests
1.
0.036 s
OK
1.
0.036 s
WRONG ANSWER,
got 5 expected 9
stdout:
Es estrella
1.
0.036 s
WRONG ANSWER,
got 7 expected 16
stdout:
Es estrella
Code: 15:33:01 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) > 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Code: 15:33:16 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) == 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Analysis
Code: 15:33:38 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) == 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Analysis
Code: 15:33:41 UTC,
py,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
def build_graph(A, B, num_nodes):
graph_built = [[] for i in range(num_nodes)]
graph_degree_nodes = num_nodes * [0]
IsStar = False
for i in range(len(A)):
graph_built[A[i]].append(B[i])
graph_built[B[i]].append(A[i])
graph_degree_nodes[A[i]] += 1
graph_degree_nodes[B[i]] += 1
Hig_degree = [val for val in graph_degree_nodes if val > 1]
if len(Hig_degree) == 1:
IsStar = True
return graph_built, IsStar
def star(graph_built, num_nodes):
num = 0
for i in range(len(graph_built)):
if len(graph_built) > 1:
num += 1
if num > 1:
return False
else:
return True
def search_node_degree_1(graph_built):
for i in range(len(graph_built)):
if len(graph_built[i]) == 1:
return i
def is_even(number):
if number % 2 == 1:
return True
else:
return False
def compute_odd_routes(graph_built, first_node, num_nodes):
distances = num_nodes*[0]
count = 0
followers = []
nodes_to_visit = [first_node]
while nodes_to_visit:
node_to_analize = nodes_to_visit.pop(0)
followers = graph_built[node_to_analize].copy()
for next_node in followers:
distances[next_node] = distances[node_to_analize] + 1
if is_even(distances[next_node]):
count += 1
graph_built[node_to_analize].remove(next_node)
graph_built[next_node].remove(node_to_analize)
nodes_to_visit.append(next_node)
return count
def solution(A, B):
num_nodes = len(A) + 1
if (num_nodes == 1):
return 0
elif (num_nodes == 2):
return 1
else:
graph_built, IsStar = build_graph(A, B, num_nodes)
if IsStar:
return (num_nodes-1)
else:
node_degree_1 = search_node_degree_1(graph_built)
odd_routes_node_degree_1 = compute_odd_routes(
graph_built, node_degree_1, num_nodes)
return ((num_nodes - odd_routes_node_degree_1) * odd_routes_node_degree_1)
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.044 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
OK
expand all
Correctness/performance tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
1.
0.740 s
OK
expand all
Performance tests
1.
0.048 s
OK
2.
0.048 s
OK
3.
0.048 s
OK
4.
0.048 s
OK
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.056 s
OK
4.
0.052 s
OK
1.
0.288 s
OK
1.
0.432 s
OK
2.
0.460 s
OK
1.
0.420 s
OK
2.
0.468 s
OK