Hi,
I struggle with AKBAR7 problem in python.
There is only 1 sec of time limit and I wonder if it is even possible to solve it.
Did any one manage to fit in time using python?
Here is my solution, which seem to be fine. If I’m correct it work in O(E+V), and I have no idea what else I can improve… 
May '24
May '24
There are no Python solvers, but two have solved with PyPy1.
(btw, nobody but you, the problem setter, and probably the admins, can see your code at the link you provided.)
Oh! I was not aware that it’s secret.
I tried with PYPY but with the same result. Still no idea what else I can improve
# https://www.spoj.com/problems/AKBAR/
# This improved version of bsf with multiple sources
import sys
from collections import deque
class Graph:
def __init__(self, n):
self.adj = [[] for _ in range(n)]
self.n = n
def bfs(g: Graph):
# variable initialization
protected_by = [None for _ in range(g.n)]
power_left = [None for _ in range(g.n)]
# setup sources (soldiers)
list_of_sources = [i for i in range(g.n) if g.soldiers[i] is not None]
non_zero_sources = [i for i in range(g.n) if g.soldiers[i] is not None and g.soldiers[i] > 0]
for i in list_of_sources:
power_left[i] = g.soldiers[i]
protected_by[i] = i
q = deque(non_zero_sources)
# Main loop
while len(q) != 0:
u = q[0]
for v in g.adj[u]:
if protected_by[v] is not None and protected_by[v] != protected_by[u]:
return -1
if protected_by[v] is None:
protected_by[v] = protected_by[u]
power_left[v] = power_left[u] - 1
if power_left[v] > 0:
q.append(v)
q.popleft()
if None in protected_by:
return -1
def verify(g: Graph):
result = bfs(g)
if result == -1:
print("No")
else:
print("Yes")
def main():
with sys.stdin as f:
# with open("input") as f:
t = int(f.readline())
for test_case in range(t):
# print(f" === Test case {test_case} ===")
n, r, m = ([int(i) for i in f.readline().split()]) # cities, roads, soldiers
g = Graph(n)
g.soldiers = [None for _ in range(n)]
for road in range(r):
a, b = ([int(i) - 1 for i in f.readline().split()])
g.adj[a].append(b)
g.adj[b].append(a)
for soldier in range(m):
city, strength = ([int(i) for i in f.readline().split()])
g.soldiers[city - 1] = strength
verify(g)
if __name__ == '__main__':
main()