— Dark mode

Aalto Competitive Programming 2024 - wk2 - Homework

Connect cities

  • Start: 2024-09-04 12:00:00
  • End: 2024-09-12 12:00:00
CSES - Aalto Competitive Programming 2024 - wk2 - Homework - Results
Submission details
Task:Connect cities
Sender:ZDHKLV
Submission time:2024-09-04 19:20:45 +0300
Language:PyPy3
Status:READY
Result:
Test results
testverdicttime
#10.04 sdetails
#20.04 sdetails
#3ACCEPTED0.04 sdetails
#40.04 sdetails
#5ACCEPTED0.04 sdetails
#60.40 sdetails
#70.40 sdetails
#80.43 sdetails
#90.40 sdetails
#100.40 sdetails
#110.16 sdetails
#120.04 sdetails

Code

N, M = input("").split(" ")
N, M = int(N), int(M)

ADJ = [[] for _ in range(N)]

for i in range(M):
    a, b = input("").split(" ")
    a, b = int(a) - 1, int(b) - 1
    ADJ[a].append(b)
    ADJ[b].append(a)

seen = [-1] * N

def dfs(k, tag):
    if seen[k] != -1:
        return
    seen[k] = tag
    for x in ADJ[k]:
        dfs(x, tag)

id = 0
for i in range(N):
    if seen[i] == -1:
        dfs(i, id)
        id += 1

components = [[] for _ in range(N) ]
P = 1

for i, tag in enumerate(seen):
    components[tag].append(i)
    P = max(tag+1, P)

additions = []
current = components[0][0]

for i in range(1, P):
    next = components[i][0]
    additions.append((current, next))
    next = current

print(len(additions))
for x, y in additions:
    print(f"{x} {y}")

Test details

Test 1

Verdict:

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

correct output
2
1 2
2 7
view save

user output
2
0 1
0 6
view save

Test 2

Verdict:

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

correct output
2
1 4
4 5
view save

user output
2
0 3
0 4
view save

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:

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

correct output
1
1 3
view save

user output
1
0 2
view save

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:

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 "input/code.py", line 24, in <module>
    dfs(i, id)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  [Previous line repeated 1446 more times]
  File "input/code.py", line 15, in dfs
    if seen[k] != -1:
RecursionError: maximum recursion depth exceeded

Test 7

Verdict:

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 "input/code.py", line 24, in <module>
    dfs(i, id)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  [Previous line repeated 1575 more times]
  File "input/code.py", line 15, in dfs
    if seen[k] != -1:
RecursionError: maximum recursion depth exceeded

Test 8

Verdict:

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 "input/code.py", line 24, in <module>
    dfs(i, id)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  [Previous line repeated 1369 more times]
  File "input/code.py", line 15, in dfs
    if seen[k] != -1:
RecursionError: maximum recursion depth exceeded

Test 9

Verdict:

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 "input/code.py", line 24, in <module>
    dfs(i, id)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  [Previous line repeated 1575 more times]
  File "input/code.py", line 15, in dfs
    if seen[k] != -1:
RecursionError: maximum recursion depth exceeded

Test 10

Verdict:

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 "input/code.py", line 24, in <module>
    dfs(i, id)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  File "input/code.py", line 19, in dfs
    dfs(x, tag)
  [Previous line repeated 1575 more times]
  File "input/code.py", line 15, in dfs
    if seen[k] != -1:
RecursionError: maximum recursion depth exceeded

Test 11

Verdict:

input
100000 1
1 2
view save

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

user output
99998
0 2
0 3
0 4
0 5
...
view save

Test 12

Verdict:

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

correct output
2
1 2
2 7
view save

user output
2
0 1
0 6
view save

Tasks

A Connect citiesB Apartments

Submissions (ZDHKLV)

2024-09-05 17:45:37 2024-09-05 17:41:40 2024-09-05 16:06:26 2024-09-04 19:27:03 2024-09-04 19:20:45