— Dark mode

E4590 2020 2

Internet connection

  • Start: 2020-09-19 13:00:00
  • End: 2020-09-19 16:00:00
Submission details
Task:Internet connection
Sender:m-x-doctor
Submission time:2020-09-19 13:29:38 +0300
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#10.08 sdetails
#20.07 sdetails
#30.08 sdetails
#40.07 sdetails
#50.08 sdetails
#60.07 sdetails
#70.07 sdetails
#80.08 sdetails
#90.07 sdetails
#100.07 sdetails
#110.07 sdetails
#120.08 sdetails
#130.07 sdetails
#140.07 sdetails
#150.07 sdetails
#160.07 sdetails
#170.07 sdetails
#180.07 sdetails
#190.08 sdetails
#200.07 sdetails
#210.07 sdetails
#220.07 sdetails

Code

"""https://cses.fi/345/task/B"""
import numpy as np


def get_path_with_dfs(adj_matrix, V):
    """DFS uses a stack/list. BFS uses a queue."""
    root = 1  # Teemu
    target = V  # Taina
    to_visit = [root]
    path = []  # Stuff you've seen.
    path_weights = []
    while to_visit:
        v = to_visit.pop()  # Pop last inserted element.
        path.append(v)
        for neighbor in range(1, V+1):
            weight = adj_matrix[v][neighbor]
            if weight <= 0 or (neighbor in path):
                continue
            if neighbor == target:
                path.append(target)
                path_weights.append(weight)
                return path, path_weights
            to_visit.append(neighbor)
    return None, None  # No path found


def max_rate(adj_matrix, V):
    total_max_rate = 0
    path, path_weights = get_path_with_dfs(adj_matrix, V)
    while path:
        max_rate = max(path_weights)
        total_max_rate += max_rate
        # Deduct the max_rate from all weights
        for i in range(len(path)-1):
            a, b = path[i], path[i+1]
            adj_matrix[a][b] -= max_rate
            adj_matrix[b][a] -= max_rate
        path, path_weights = get_path_with_dfs(adj_matrix, V)

    print(int(total_max_rate))
    return


# Read number oof vertices (computers) and edges (connections).
V, E = [int(x) for x in input().split()]
adj_matrix = np.zeros((V+1, V+1))
for i in range(E):
    a, b, weight = [int(x) for x in input().split()]
    adj_matrix[a][b] = weight
    adj_matrix[b][a] = weight
max_rate(adj_matrix, V)

Test details

Test 1

Verdict:

input
10 20
5 6 19
4 5 47
3 5 7
4 9 62
...
view save

correct output
73
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 2

Verdict:

input
10 20
2 4 63
7 9 54
6 7 16
2 3 9
...
view save

correct output
110
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 3

Verdict:

input
10 20
5 6 90
2 3 46
7 8 80
6 7 60
...
view save

correct output
29
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 4

Verdict:

input
10 20
3 4 76
5 7 8
3 8 71
4 7 24
...
view save

correct output
95
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 5

Verdict:

input
10 20
1 8 22
6 7 40
4 5 20
8 10 77
...
view save

correct output
156
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 6

Verdict:

input
100 1000
63 85 864540192
22 91 974117435
64 66 953124912
85 88 6080960
...
view save

correct output
4397669179
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 7

Verdict:

input
100 1000
36 93 760720873
12 75 175717522
78 79 340128710
80 83 181753465
...
view save

correct output
5298558023
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 8

Verdict:

input
100 1000
20 60 909693891
55 91 570199535
21 41 118646902
37 82 824735480
...
view save

correct output
5466229311
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 9

Verdict:

input
100 1000
26 44 753330451
62 67 821574279
70 95 219303983
7 44 980013084
...
view save

correct output
4893925638
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 10

Verdict:

input
100 1000
15 89 501388091
50 71 396801720
15 92 324349822
29 85 184420157
...
view save

correct output
6956499595
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 11

Verdict:

input
2 1
1 2 1
view save

correct output
1
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 12

Verdict:

input
2 1
2 1 1
view save

correct output
0
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 13

Verdict:

input
2 2
1 2 1
2 1 1
view save

correct output
1
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 14

Verdict:

input
100 1000
1 2 539540023
2 3 244306651
3 4 253259012
3 5 630461598
...
view save

correct output
0
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 15

Verdict:

input
4 5
1 2 2
1 3 5
2 4 3
3 2 2
...
view save

correct output
4
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 16

Verdict:

input
2 0
view save

correct output
0
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 17

Verdict:

input
100 0
view save

correct output
0
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 18

Verdict:

input
100 196
1 2 1000000000
2 100 1000000000
1 3 1000000000
3 100 1000000000
...
view save

correct output
98000000000
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 19

Verdict:

input
100 99
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
...
view save

correct output
1000000000
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 20

Verdict:

input
2 2
2 1 1
1 2 1
view save

correct output
1
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 21

Verdict:

input
4 6
1 2 1000000000
1 3 1000000000
2 3 1
2 4 1000000000
...
view save

correct output
2000000000
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Test 22

Verdict:

input
4 6
1 2 1000000000
1 3 1000000000
2 4 1000000000
2 3 1
...
view save

correct output
2000000000
view save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 2, in <module>
    import...

Tasks

A Alien Invasion IIB Internet connectionC Congested uploadsD Swapping lettersE 3SAT solverF Densest subgraphG Grid Paths IIH Easier Grid Paths

Submissions (m-x-doctor)

2020-09-20 11:15:15 2020-09-19 15:31:44 2020-09-19 15:29:58 2020-09-19 14:22:49 2020-09-19 14:21:35 2020-09-19 14:20:27 2020-09-19 13:38:53 2020-09-19 13:29:38