Task: | Connect cities |
Sender: | Mojojijo |
Submission time: | 2024-09-09 11:24:05 +0300 |
Language: | Python3 (CPython3) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.02 s | details |
#2 | WRONG ANSWER | 0.02 s | details |
#3 | ACCEPTED | 0.02 s | details |
#4 | WRONG ANSWER | 0.02 s | details |
#5 | ACCEPTED | 0.02 s | details |
#6 | WRONG ANSWER | 0.60 s | details |
#7 | WRONG ANSWER | 0.62 s | details |
#8 | WRONG ANSWER | 0.61 s | details |
#9 | WRONG ANSWER | 0.62 s | details |
#10 | WRONG ANSWER | 0.61 s | details |
#11 | WRONG ANSWER | 0.02 s | details |
#12 | WRONG ANSWER | 0.02 s | details |
Code
def connect_cities(n, roads):from collections import defaultdict# Adjacency listgraph = defaultdict(list)for a,b in roads:graph[a].append(b)graph[b].append(a)visited = [False] * (n+1)components =[]def dfs(node, component):visited[node] = Truecomponent.append(node)for neighbour in graph[node]:if not visited[neighbour]:dfs(neighbour, component)for i in range(1, n+1):if not visited[i]:component = []dfs(i, component)components.append(component)return componentsdef find_roads_to_add(n, roads):components = connect_cities(n, roads)# If there's only one component, no new roads are neededif len(components) == 1:print(0)return# We need to connect each component to the next onerequired_roads = []for i in range(len(components) - 1):# Connect the first city in component[i] to the first city in component[i+1]city1 = components[i][0]city2 = components[i+1][0]required_roads.append((city1, city2))# Step 5: Output the number of roads and the roads themselvesprint(len(required_roads))for road in required_roads:print(road[0], road[1])n,m = map(int,input().split())roads = []for _ in range(m):a,b = map(int,input().split())roads.append((a,b))print(roads)# find_roads_to_add(n, roads)
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
10 10 2 5 5 6 1 4 6 8 ... |
correct output |
---|
2 1 2 2 7 |
user output |
---|
[(2, 5), (5, 6), (1, 4), (6, 8... |
Test 2
Verdict: WRONG ANSWER
input |
---|
10 10 3 9 6 8 9 10 7 8 ... |
correct output |
---|
2 1 4 4 5 |
user output |
---|
[(3, 9), (6, 8), (9, 10), (7, ... |
Test 3
Verdict: ACCEPTED
input |
---|
10 10 7 9 1 7 1 3 3 4 ... |
correct output |
---|
0 |
user output |
---|
[(7, 9), (1, 7), (1, 3), (3, 4... |
Test 4
Verdict: WRONG ANSWER
input |
---|
10 10 4 8 5 9 4 9 2 7 ... |
correct output |
---|
1 1 3 |
user output |
---|
[(4, 8), (5, 9), (4, 9), (2, 7... |
Test 5
Verdict: ACCEPTED
input |
---|
10 10 4 9 2 4 7 10 1 8 ... |
correct output |
---|
0 |
user output |
---|
[(4, 9), (2, 4), (7, 10), (1, ... |
Test 6
Verdict: WRONG ANSWER
input |
---|
100000 200000 7233 22146 94937 96203 6133 10731 98737 99193 ... |
correct output |
---|
4785 1 2 2 3 3 4 4 5 ... |
user output |
---|
[(7233, 22146), (94937, 96203)... Truncated |
Test 7
Verdict: WRONG ANSWER
input |
---|
100000 200000 92950 93575 24401 88897 41796 99364 47106 50330 ... |
correct output |
---|
4868 1 2 2 7 7 9 9 15 ... |
user output |
---|
[(92950, 93575), (24401, 88897... Truncated |
Test 8
Verdict: WRONG ANSWER
input |
---|
100000 200000 15637 76736 79169 98809 4382 86557 73383 77029 ... |
correct output |
---|
4683 1 9 9 20 20 27 27 28 ... |
user output |
---|
[(15637, 76736), (79169, 98809... Truncated |
Test 9
Verdict: WRONG ANSWER
input |
---|
100000 200000 47932 66981 86401 99942 4353 27841 60492 67345 ... |
correct output |
---|
4807 1 6 6 7 7 11 11 12 ... |
user output |
---|
[(47932, 66981), (86401, 99942... Truncated |
Test 10
Verdict: WRONG ANSWER
input |
---|
100000 200000 6554 44548 76413 98555 5447 59589 70166 74434 ... |
correct output |
---|
4786 1 2 2 18 18 21 21 27 ... |
user output |
---|
[(6554, 44548), (76413, 98555)... Truncated |
Test 11
Verdict: WRONG ANSWER
input |
---|
100000 1 1 2 |
correct output |
---|
99998 1 3 3 4 4 5 5 6 ... |
user output |
---|
[(1, 2)] |
Test 12
Verdict: WRONG ANSWER
input |
---|
10 9 2 5 5 6 1 4 6 8 ... |
correct output |
---|
2 1 2 2 7 |
user output |
---|
[(2, 5), (5, 6), (1, 4), (6, 8... |