CSES - Aalto Competitive Programming 2024 - wk2 - Homework

CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results

Submission details
Task:	Connect cities
Sender:	clovis
Submission time:	2024-09-07 18:13:24 +0300
Language:	CPython3
Status:	READY
Result:	RUNTIME ERROR

Test results
test	verdict	time
#1	RUNTIME ERROR	0.02 s	details
#2	RUNTIME ERROR	0.02 s	details
#3	ACCEPTED	0.02 s	details
#4	RUNTIME ERROR	0.02 s	details
#5	ACCEPTED	0.02 s	details
#6	RUNTIME ERROR	0.82 s	details
#7	RUNTIME ERROR	0.83 s	details
#8	RUNTIME ERROR	0.83 s	details
#9	RUNTIME ERROR	0.83 s	details
#10	RUNTIME ERROR	0.81 s	details
#11	RUNTIME ERROR	0.02 s	details
#12	RUNTIME ERROR	0.02 s	details

Code

def findRoadsToBuild(cityMappingDict, n):
  graphs = []
  visited = set()

  for city in range(1, n + 1):
    if city not in visited:
      graph = []
      dfs(city, cityMappingDict, visited, graph)
      graphs.append(graph)

  # print("Graphs:", graphs)

  roadsToBuildList = []
  for i in range(len(graphs) - 1):
    roadsToBuildList.append((graphs[i - 1][0], graphs[i][0]))

  return roadsToBuildList

def dfs(city, cityMappingDict, visited, graph):
  visited.add(city)
  graph.append(city)
  for neighbour in cityMappingDict[city]:
    if neighbour not in visited:
      dfs(neighbour, cityMappingDict, visited, graph)


# first line, n (number of cities) and m (number of roads)
numCitiesNumRoadsInput = input().split()
n = int(numCitiesNumRoadsInput[0])
m = int(numCitiesNumRoadsInput[1])

if n == 1:
  print(0)
elif n == 2 and m == 1:
  print(0)
else:
  # initialise dict to act as an adjacency list
  cityMappingDict = dict()

  # subsequent lines, roads connecting cities
  for i in range(m):
    cityRoadConnectionString = input().split()
    leftCity = int(cityRoadConnectionString[0])
    rightCity = int(cityRoadConnectionString[1])
    leftCityList = cityMappingDict.get(leftCity, [])
    leftCityList.append(rightCity)
    cityMappingDict[leftCity] = leftCityList

    rightCityList = cityMappingDict.get(rightCity, [])
    rightCityList.append(leftCity)
    cityMappingDict[rightCity] = rightCityList

  newRoads = findRoadsToBuild(cityMappingDict, n)

  print(len(newRoads))

  for newRoad in newRoads:
    print(newRoad[0], newRoad[1])

Test details

Test 1

Verdict: RUNTIME ERROR

input
`10 10 2 5 5 6 1 4 6 8 ...` view save

correct output
`2 1 2 2 7` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 22, in dfs
    for neighbour in cityMappingDict[city]:
KeyError: 7

Test 2

Verdict: RUNTIME ERROR

input
`10 10 3 9 6 8 9 10 7 8 ...` view save

correct output
`2 1 4 4 5` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 22, in dfs
    for neighbour in cityMappingDict[city]:
KeyError: 4

Test 3

Verdict: ACCEPTED

input
`10 10 7 9 1 7 1 3 3 4 ...` view save

correct output
`0` view save

user output
`0` view save

Test 4

Verdict: RUNTIME ERROR

input
`10 10 4 8 5 9 4 9 2 7 ...` view save

correct output
`1 1 3` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 22, in dfs
    for neighbour in cityMappingDict[city]:
KeyError: 3

Test 5

Verdict: ACCEPTED

input
`10 10 4 9 2 4 7 10 1 8 ...` view save

correct output
`0` view save

user output
`0` view save

Test 6

Verdict: RUNTIME ERROR

input
`100000 200000 7233 22146 94937 96203 6133 10731 98737 99193 ...` view save

correct output
`4785 1 2 2 3 3 4 4 5 ...` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 22, in dfs
    for neighbour in cityMappingDict[city]:
KeyError: 1

Test 7

Verdict: RUNTIME ERROR

input
`100000 200000 92950 93575 24401 88897 41796 99364 47106 50330 ...` view save

correct output
`4868 1 2 2 7 7 9 9 15 ...` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 22, in dfs
    for neighbour in cityMappingDict[city]:
KeyError: 1

Test 8

Verdict: RUNTIME ERROR

input
`100000 200000 15637 76736 79169 98809 4382 86557 73383 77029 ...` view save

correct output
`4683 1 9 9 20 20 27 27 28 ...` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  [Previous line repeated 994 more times]
  File "/box/input/code.py", line 20, in dfs
    visited.add(city)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 9

Verdict: RUNTIME ERROR

input
`100000 200000 47932 66981 86401 99942 4353 27841 60492 67345 ...` view save

correct output
`4807 1 6 6 7 7 11 11 12 ...` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  [Previous line repeated 994 more times]
  File "/box/input/code.py", line 20, in dfs
    visited.add(city)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 10

Verdict: RUNTIME ERROR

input
`100000 200000 6554 44548 76413 98555 5447 59589 70166 74434 ...` view save

correct output
`4786 1 2 2 18 18 21 21 27 ...` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 24, in dfs
    dfs(neighbour, cityMappingDict, visited, graph)
  [Previous line repeated 994 more times]
  File "/box/input/code.py", line 20, in dfs
    visited.add(city)
RecursionError: maximum recursion depth exceeded while calling a Python object

Test 11

Verdict: RUNTIME ERROR

input
`100000 1 1 2` view save

correct output
`99998 1 3 3 4 4 5 5 6 ...` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 22, in dfs
    for neighbour in cityMappingDict[city]:
KeyError: 3

Test 12

Verdict: RUNTIME ERROR

input
`10 9 2 5 5 6 1 4 6 8 ...` view save

correct output
`2 1 2 2 7` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "/box/input/code.py", line 53, in <module>
    newRoads = findRoadsToBuild(cityMappingDict, n)
  File "/box/input/code.py", line 8, in findRoadsToBuild
    dfs(city, cityMappingDict, visited, graph)
  File "/box/input/code.py", line 22, in dfs
    for neighbour in cityMappingDict[city]:
KeyError: 7

Aalto Competitive Programming 2024 - wk2 - Homework

Connect cities

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Tasks

Submissions (clovis)