fork download
copy 
  1. import collections
  2.  
  3. class SatelliteNetwork:
  4.     def __init__(self):
  5.         self.connected_satellites = set()
  6.         self.adjacency_list = collections.defaultdict(list)
  7.  
  8.     def on_satellite_reported_back(self, satellite_id: int):
  9.         print(f"SatelliteReportedBack: {satellite_id}")
  10.  
  11.     def err_duplicate_satellite(self, satellite_id: int):
  12.         print(f"ErrDuplicateSatellite: {satellite_id}")
  13.  
  14.     def err_invalid_satellite(self, satellite_id: int):
  15.         print(f"ErrInvalidSatellite: {satellite_id}")
  16.  
  17.     def satellite_connected(self, satellite_id: int):
  18.         if satellite_id in self.connected_satellites:
  19.             self.err_duplicate_satellite(satellite_id)
  20.             return
  21.         self.connected_satellites.add(satellite_id)
  22.  
  23.     def relationship_established(self, sat_id1: int, sat_id2: int):
  24.         error_found = False
  25.         if sat_id1 not in self.connected_satellites:
  26.             self.err_invalid_satellite(sat_id1)
  27.             error_found = True
  28.         if sat_id2 not in self.connected_satellites:
  29.             self.err_invalid_satellite(sat_id2)
  30.             error_found = True
  31.         if error_found:
  32.             return
  33.         self.adjacency_list[sat_id1].append(sat_id2)
  34.         self.adjacency_list[sat_id2].append(sat_id1)
  35.  
  36.     def message_received(self, m: int, initial_satellites: list[int]):
  37.         for sat_id in initial_satellites:
  38.             if sat_id not in self.connected_satellites:
  39.                 self.err_invalid_satellite(sat_id)
  40.                 return
  41.  
  42.         time_of_receipt = {}
  43.         bfs_queue = collections.deque()
  44.  
  45.         for sat_id in set(initial_satellites):
  46.             if sat_id not in time_of_receipt:
  47.                 time_of_receipt[sat_id] = 0
  48.                 bfs_queue.append((sat_id, 0))
  49.  
  50.         while bfs_queue:
  51.             u_id, u_time = bfs_queue.popleft()
  52.             for v_id in sorted(self.adjacency_list[u_id]):
  53.                 if v_id not in time_of_receipt:
  54.                     v_time = u_time + 10
  55.                     time_of_receipt[v_id] = v_time
  56.                     bfs_queue.append((v_id, v_time))
  57.  
  58.         reports = []
  59.         for sat_id in time_of_receipt:
  60.             receipt_time_self = time_of_receipt[sat_id]
  61.  
  62.             last_neighbor_receipt_time = 0
  63.             for neighbor_id in self.adjacency_list[sat_id]:
  64.                 if neighbor_id in time_of_receipt:
  65.                     last_neighbor_receipt_time = max(
  66.                         last_neighbor_receipt_time, 
  67.                         time_of_receipt[neighbor_id]
  68.                     )
  69.  
  70.             processing_start_time = max(receipt_time_self, last_neighbor_receipt_time)
  71.             final_report_time = processing_start_time + 30
  72.             reports.append((final_report_time, sat_id))
  73.  
  74.         reports.sort()
  75.  
  76.         for report_time, satellite_id in reports:
  77.             self.on_satellite_reported_back(satellite_id)
  78.  
  79. if __name__ == '__main__':
  80.     network = SatelliteNetwork()
  81.  
  82.     print("--- Processing Sample Case 0 ---")
  83.     # Setup for Sample Case 0
  84.     network_case0 = SatelliteNetwork()
  85.     network_case0.satellite_connected(1)
  86.     network_case0.satellite_connected(2)
  87.     network_case0.satellite_connected(3)
  88.     network_case0.relationship_established(2, 1)
  89.     network_case0.message_received(1, [2])
  90.     print("-" * 20)
  91.  
  92.     print("--- Processing Custom Test Case ---")
  93.     network_case1 = SatelliteNetwork()
  94.     network_case1.satellite_connected(1)
  95.     network_case1.satellite_connected(2)
  96.     network_case1.satellite_connected(3)
  97.     network_case1.satellite_connected(4)
  98.     network_case1.satellite_connected(5)
  99.     network_case1.satellite_connected(6)
  100.     network_case1.relationship_established(1, 2)
  101.     network_case1.relationship_established(2, 3)
  102.     network_case1.relationship_established(3, 4)
  103.     network_case1.relationship_established(4, 5)
  104.     network_case1.relationship_established(5, 6)
  105.     network_case1.message_received(1, [1])
  106.     print("-" * 20)
Success #stdin #stdout 0.09s 14176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
--- Processing Sample Case 0 ---
SatelliteReportedBack: 1
SatelliteReportedBack: 2
--------------------
--- Processing Custom Test Case ---
SatelliteReportedBack: 1
SatelliteReportedBack: 2
SatelliteReportedBack: 3
SatelliteReportedBack: 4
SatelliteReportedBack: 5
SatelliteReportedBack: 6
--------------------
https://ideone.com/vu1Z5H
language:
Python 3 (python  3.12)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!