CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:jmarttinen
Submission time:2021-10-05 09:44:14
Language:PyPy3
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.13 s1, 2, 3details
#20.20 s2, 3details
#3--3details

Code



n = int(input())
graph_dict = {i : [] for i in range(1, n+1)}
graph = []
for _ in range(n-1):
    inp = tuple(map(int, input().split()))
    graph.append(inp)
    graph_dict[inp[0]].append(inp[1])
    graph_dict[inp[1]].append(inp[0])



def search_main():
    s = 0

    graph.sort(key=lambda x: x[2])
    while len(graph) > 0:
        l,r = 1, 1
        m = graph[0]
        graph.pop(0)
        graph_dict[m[0]].remove(m[1])
        graph_dict[m[1]].remove(m[0])

        for n in graph_dict[m[0]]:
            l += search(n, [m[0]])
        
        for n in graph_dict[m[1]]:
            r += search(n, [m[1]])

        s += l*r * m[2]

    return s
        
def search(node, checked=[]):
    if len(list(filter(lambda x: x not in checked, graph_dict[node]))) == 0:
        return 1
    l = 0
    for n in graph_dict[node]:
        checked.append(n)
        l += search(n, checked)
    return l

print(search_main())

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 45, in <module>
    print(search_main())
  File "input/code.py", line 27, in search_main
    l += search(n, [m[0]])
  File "input/code.py", line 42, in search
    l += search(n, checked)
  File "input/code.py", line 42, in search
    l += search(n, checked)
  File "input/code.py", line 42, in search
    l += search(n, checked)
  [Previous line repeated 1885 more times]
  File "input/code.py", line 37, in search
    if len(list(filter(lambda x: x not in checked, graph_dict[node]))) == 0:
RecursionError: maximum recursion depth exceeded

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 45, in <module>
    print(search_main())
  File "input/code.py", line 27, in search_main
    l += search(n, [m[0]])
  File "input/code.py", line 42, in search
    l += search(n, checked)
  File "input/code.py", line 42, in search
    l += search(n, checked)
  File "input/code.py", line 42, in search
    l += search(n, checked)
  [Previous line repeated 1884 more times]
  File "input/code.py", line 37, in search
    if len(list(filter(lambda x: x not in checked, graph_dict[node]))) == 0:
  File "input/code.py", line 37, in <lambda>
    if len(list(filter(lambda x: x not in checked, graph_dict[node]))) == 0:
RecursionError: maximum recursion depth exceeded

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)