CSES - Aalto Competitive Programming 2024 - wk4 - Wed - Results
Submission details
Task:Conurbation
Sender:aalto2024d_001
Submission time:2024-09-25 17:36:10 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#80.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#160.00 sdetails
#170.00 sdetails
#180.00 sdetails
#190.00 sdetails
#200.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#260.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#340.00 sdetails
#350.00 sdetails
#360.00 sdetails
#370.00 sdetails
#380.00 sdetails
#390.00 sdetails
#400.00 sdetails
#410.00 sdetails
#420.01 sdetails
#430.01 sdetails
#440.01 sdetails
#450.01 sdetails
#460.01 sdetails
#470.00 sdetails
#480.01 sdetails
#490.00 sdetails
#500.01 sdetails
#510.00 sdetails
#520.02 sdetails
#530.02 sdetails
#540.02 sdetails
#550.02 sdetails
#560.03 sdetails
#570.01 sdetails
#580.03 sdetails
#590.01 sdetails
#600.02 sdetails
#610.62 sdetails
#620.63 sdetails
#630.58 sdetails
#640.59 sdetails
#650.69 sdetails
#660.54 sdetails
#670.69 sdetails
#680.54 sdetails
#690.62 sdetails

Code

#include <iostream>
#include <vector>
using namespace std;

int find(vector<int>& link, int x) {
    if (x != link[x]) {
        link[x] = find(link, link[x]);
    }
    return link[x];
}

void unite(vector<int>& size, vector<int>& population, vector<int>& link, int a, int b, int added_population) {
    a = find(link, a);
    b = find(link, b);
    if (a != b) {
        if (size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        population[a] += population[b] + added_population;
        link[b] = a;
    } else {
        population[a] += added_population;
    }
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> u(m), v(m), w(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        u[i]--; 
        v[i]--;
    }

    vector<int> x(q), y(q);
    for (int i = 0; i < q; i++) {
        cin >> x[i] >> y[i];
        x[i]--; 
        y[i]--; 
    }

    vector<int> link(n), size(n, 1), population(n);
    for (int i = 0; i < n; i++) {
        link[i] = i;
        population[i] = a[i];
    }

    vector<vector<int>> populationYear(m+1, vector<int>(n));
    for (int i = 0; i < n; i++) {
        populationYear[0][i] = population[find(link, i)];
    }

    for (int i = 0; i < m; i++) {
        unite(size, population, link, u[i], v[i], w[i]);
        for (int j = 0; j < n; j++) {
            populationYear[i+1][j] = population[find(link, j)];
        }
    }

    for (int i = 0; i < q; i++) {
        cout << populationYear[y[i]][x[i]] << " ";
    }

    return 0;
}

Test details

Test 1

Verdict:

input
2 1 3
6 10 
1 2 6
1 1
2 1
...

correct output
22 22 22 

user output
6 10 10 

Test 2

Verdict:

input
2 1 3
5 3 
1 2 9
2 1
2 1
...

correct output
17 17 17 

user output
3 3 5 

Test 3

Verdict:

input
2 1 4
1 4 
1 2 7
1 1
2 1
...

correct output
12 12 12 12 

user output
1 4 4 1 

Test 4

Verdict:

input
3 1 8
6 5 1 
1 2 10
3 1
2 1
...

correct output
1 21 21 1 21 1 21 1 

user output
1 5 5 1 6 1 5 1 

Test 5

Verdict:

input
3 2 7
3 10 8 
1 2 8
1 3 7
2 2
...

correct output
36 21 21 8 21 36 36 

user output
21 10 10 8 10 8 21 

Test 6

Verdict:

input
3 3 5
9 6 2 
1 2 1
1 3 5
2 3 9
...

correct output
16 2 23 32 32 

user output
9 2 16 23 23 

Test 7

Verdict:

input
3 1 4
10 6 2 
1 2 5
2 1
2 1
...

correct output
21 21 21 21 

user output
6 6 10 10 

Test 8

Verdict:

input
4 6 8
2 3 1 1 
1 2 5
1 3 1
1 4 9
...

correct output
34 34 1 1 1 22 25 37 

user output
25 25 1 1 1 12 22 34 

Test 9

Verdict:

input
4 4 11
7 9 4 9 
1 4 9
2 3 8
2 4 1
...

correct output
9 25 25 56 25 25 25 25 56 4 4 

user output
9 25 25 47 9 7 9 25 47 4 4 

Test 10

Verdict:

input
4 6 5
7 9 8 10 
1 2 9
1 3 2
1 4 3
...

correct output
58 60 25 58 60 

user output
51 58 7 51 58 

Test 11

Verdict:

input
4 4 7
6 6 9 8 
1 3 1
1 4 1
2 3 5
...

correct output
25 16 44 36 6 44 36 

user output
16 9 36 25 6 36 6 

Test 12

Verdict:

input
5 7 12
7 1 4 9 10 
1 2 8
1 5 2
2 3 9
...

correct output
50 74 9 69 4 82 9 41 4 74 9 50...

user output
41 69 9 9 4 74 9 28 4 69 9 41 

Test 13

Verdict:

input
5 10 12
6 9 9 9 9 
1 2 1
1 3 9
1 4 1
...

correct output
68 58 34 44 34 75 58 16 68 68 ...

user output
59 56 9 9 16 68 56 6 59 59 9 5...

Test 14

Verdict:

input
5 3 5
7 7 9 6 7 
1 2 2
2 3 5
3 5 6
...

correct output
9 6 43 30 43 

user output
9 6 30 9 30 

Test 15

Verdict:

input
5 2 12
6 9 5 9 1 
1 3 2
2 5 1
2 1
...

correct output
9 13 13 13 13 9 9 9 13 13 13 9...

user output
9 6 13 6 5 9 9 9 13 13 13 9 

Test 16

Verdict:

input
5 10 11
4 3 1 6 3 
1 2 7
1 3 1
1 4 9
...

correct output
1 58 71 44 69 58 44 71 44 69 6...

user output
1 51 69 31 67 51 3 69 31 67 58...

Test 17

Verdict:

input
5 2 14
1 7 4 8 4 
2 5 6
3 5 5
2 2
...

correct output
26 1 1 8 4 1 17 17 4 26 8 4 26...

user output
17 1 1 8 4 1 4 7 4 17 8 4 4 7 

Test 18

Verdict:

input
5 10 8
7 8 5 6 6 
1 2 2
1 3 1
1 4 10
...

correct output
56 68 68 68 68 76 76 48 

user output
53 59 59 59 59 68 68 39 

Test 19

Verdict:

input
5 4 13
6 7 9 9 4 
1 3 4
2 3 4
3 5 1
...

correct output
35 35 30 51 4 51 9 51 7 51 51 ...

user output
30 4 7 35 4 35 9 35 7 35 35 19...

Test 20

Verdict:

input
5 2 15
9 3 5 1 7 
2 3 5
2 5 8
3 1
...

correct output
13 28 28 13 28 1 1 1 13 13 28 ...

user output
5 13 13 5 13 1 1 1 5 3 7 3 3 9...

Test 21

Verdict:

input
5 5 10
10 7 8 6 2 
1 2 9
1 3 2
1 4 7
...

correct output
61 2 61 67 49 67 67 67 26 49 

user output
49 2 49 61 6 61 61 61 10 36 

Test 22

Verdict:

input
10 14 25
10 8 2 9 9 10 5 8 9 5 
1 4 6
1 7 8
1 9 7
...

correct output
9 8 8 95 8 101 8 101 150 121 9...

user output
9 8 8 93 8 95 8 95 145 101 9 7...

Test 23

Verdict:

input
10 20 25
5 6 2 7 3 4 2 7 8 9 
1 3 5
1 7 1
1 9 1
...

correct output
71 6 4 117 54 71 99 4 112 24 1...

user output
54 6 4 115 41 54 96 4 104 15 1...

Test 24

Verdict:

input
10 7 10
6 2 8 8 3 9 6 5 5 9 
2 3 2
2 7 1
3 5 10
...

correct output
3 6 47 47 19 65 59 8 32 47 

user output
3 6 32 9 12 59 47 8 3 32 

Test 25

Verdict:

input
10 6 24
3 1 1 5 7 1 2 5 5 7 
1 2 3
1 3 3
2 6 4
...

correct output
7 5 7 7 1 5 16 1 7 5 5 11 5 5 ...

user output
7 5 7 7 1 5 1 1 7 5 5 1 5 5 40...

Test 26

Verdict:

input
10 19 21
5 2 5 1 1 7 2 2 9 8 
1 2 9
1 3 5
1 8 10
...

correct output
1 104 117 2 38 111 1 107 91 26...

user output
1 91 113 2 2 110 1 104 82 5 7 ...

Test 27

Verdict:

input
10 5 28
4 6 5 3 10 2 9 1 7 8 
1 7 9
3 9 5
4 8 3
...

correct output
7 17 10 17 22 2 2 5 5 17 35 6 ...

user output
7 5 10 17 22 2 2 5 5 17 17 6 6...

Test 28

Verdict:

input
10 20 16
3 3 9 8 5 10 6 3 8 7 
1 5 8
1 6 6
1 10 8
...

correct output
132 120 164 9 120 172 172 90 4...

user output
129 107 160 9 107 164 164 74 4...

Test 29

Verdict:

input
10 8 26
9 9 4 4 4 1 7 3 7 10 
1 5 7
3 5 3
3 6 4
...

correct output
3 85 7 9 85 10 51 81 71 9 9 41...

user output
3 81 7 9 3 10 41 71 51 9 9 32 ...

Test 30

Verdict:

input
10 5 30
5 6 9 5 10 6 2 6 8 8 
1 5 5
3 9 8
4 6 9
...

correct output
20 25 8 5 25 20 8 6 5 20 25 20...

user output
20 25 8 5 9 20 8 6 5 20 25 20 ...

Test 31

Verdict:

input
10 10 20
8 6 2 9 2 7 10 6 6 8 
1 2 10
1 3 4
1 8 7
...

correct output
110 130 30 76 130 89 110 130 8...

user output
102 110 24 65 110 76 102 110 8...

Test 32

Verdict:

input
100 187 219
74 46 50 98 23 69 26 9 6 6 44 ...

correct output
60969 25642 39518 11438 50148 ...

user output
60534 25002 36598 11372 49162 ...
Truncated

Test 33

Verdict:

input
100 154 300
20 94 59 38 98 6 85 75 24 30 5...

correct output
46 77 76 68840 2 10 53 10 1355...

user output
46 77 76 68218 2 10 53 10 17 2...
Truncated

Test 34

Verdict:

input
100 159 137
30 59 62 100 96 44 45 37 21 88...

correct output
32922 36267 13295 4921 25077 5...

user output
27546 36011 13295 4921 24831 5...
Truncated

Test 35

Verdict:

input
100 188 114
98 52 51 37 83 27 8 81 48 91 7...

correct output
896 38 38016 75 929 55318 5531...

user output
896 38 37492 75 929 53650 5531...
Truncated

Test 36

Verdict:

input
100 292 281
28 36 41 54 58 1 12 54 80 36 3...

correct output
77560 25 83317 35 47239 42343 ...

user output
76565 25 83220 35 46275 41807 ...
Truncated

Test 37

Verdict:

input
100 105 111
36 58 93 79 96 84 41 25 90 86 ...

correct output
25 41638 83 11 578 35 37057 51...

user output
25 41638 83 11 578 35 36996 51...
Truncated

Test 38

Verdict:

input
100 274 290
84 5 74 40 28 45 73 16 32 18 1...

correct output
33 111825 139106 48081 95088 7...

user output
33 111682 138260 47026 94558 7...
Truncated

Test 39

Verdict:

input
100 69 145
85 84 14 54 31 4 47 10 75 80 4...

correct output
1003 2691 46 54 45 85 1996 385...

user output
1003 2691 46 54 45 85 1996 385...
Truncated

Test 40

Verdict:

input
100 269 102
86 49 22 66 7 8 41 68 97 52 15...

correct output
94382 66968 26853 65546 61406 ...

user output
93730 66099 26786 64960 60726 ...
Truncated

Test 41

Verdict:

input
100 52 173
6 41 4 68 17 24 80 18 17 13 14...

correct output
1206 35 22 100 19 11 36 79 139...

user output
1206 35 22 100 19 11 36 79 139...
Truncated

Test 42

Verdict:

input
200 374 437
83 16 91 100 82 9 16 10 63 64 ...

correct output
7 131256 124647 183516 133600 ...

user output
7 130365 123983 182619 132572 ...
Truncated

Test 43

Verdict:

input
200 308 599
26 22 12 45 20 49 50 34 73 1 2...

correct output
101488 71 87 16319 31 100814 8...

user output
101488 71 87 16319 31 100168 8...
Truncated

Test 44

Verdict:

input
200 318 274
25 10 95 52 56 33 36 87 1 75 2...

correct output
128489 72606 464 145651 6 1079...

user output
127979 71835 464 144959 6 1069...
Truncated

Test 45

Verdict:

input
200 375 228
89 11 30 47 39 38 98 62 44 89 ...

correct output
161772 9 172295 112826 77 1522...

user output
161647 9 172067 112139 77 1521...
Truncated

Test 46

Verdict:

input
200 584 561
16 3 98 85 5 99 11 18 17 49 99...

correct output
71 118148 217768 55 89638 1898...

user output
71 117303 217269 55 89423 1897...
Truncated

Test 47

Verdict:

input
200 211 222
50 62 65 90 51 64 17 81 65 37 ...

correct output
20 60 83 101039 109091 2 1818 ...

user output
20 60 83 99731 108234 2 1818 1...
Truncated

Test 48

Verdict:

input
200 547 579
6 43 20 80 81 12 92 5 63 70 9 ...

correct output
84 114794 252841 255378 279356...

user output
84 113078 251975 255130 279267...
Truncated

Test 49

Verdict:

input
200 138 291
81 95 55 35 17 71 4 47 29 39 8...

correct output
25 54 26334 60 67 45 3437 991 ...

user output
25 54 26334 60 67 45 3437 991 ...
Truncated

Test 50

Verdict:

input
200 537 204
70 14 20 26 78 8 79 67 90 86 9...

correct output
272553 159000 231656 124672 79...

user output
272398 158636 230815 124615 79...
Truncated

Test 51

Verdict:

input
200 105 346
85 74 55 46 27 77 58 73 32 81 ...

correct output
98 93 91 470 37 3 17 1141 15 1...

user output
98 93 91 58 37 3 17 1141 15 10...
Truncated

Test 52

Verdict:

input
1000 1872 2186
84 80 33 96 11 12 9 82 94 68 1...

correct output
213572 583269 845186 159953 87...

user output
210806 583106 844946 159953 87...
Truncated

Test 53

Verdict:

input
1000 1542 2995
56 73 91 44 87 94 34 82 3 37 8...

correct output
195264 59 1415 799110 64 15852...

user output
195264 59 1415 798740 64 15852...
Truncated

Test 54

Verdict:

input
1000 1590 1370
44 84 98 61 27 84 7 70 25 65 4...

correct output
31 65 701570 560095 388274 16 ...

user output
31 65 701089 559106 387629 16 ...
Truncated

Test 55

Verdict:

input
1000 1877 1141
25 11 88 77 91 36 62 61 79 84 ...

correct output
495761 78 455001 722437 81 371...

user output
495517 78 455001 721389 81 371...
Truncated

Test 56

Verdict:

input
1000 2918 2802
31 18 99 81 27 61 3 24 93 76 3...

correct output
1147264 289548 798155 824295 4...

user output
1146580 288680 797813 824128 4...
Truncated

Test 57

Verdict:

input
1000 1055 1110
50 42 74 15 11 36 43 92 70 59 ...

correct output
86 46 70 400514 48 462515 96 2...

user output
86 46 70 400455 48 461170 96 2...
Truncated

Test 58

Verdict:

input
1000 2733 2895
84 7 16 7 52 67 52 11 18 12 25...

correct output
626156 300086 1144633 117105 1...

user output
625851 297961 1144420 116983 1...
Truncated

Test 59

Verdict:

input
1000 690 1454
40 86 79 58 75 14 93 78 70 29 ...

correct output
335 52 85 54 2458 1476 252478 ...

user output
335 52 85 54 2458 1476 251090 ...
Truncated

Test 60

Verdict:

input
1000 2684 1022
84 61 85 9 99 16 21 21 59 97 2...

correct output
1263182 290251 628913 1333935 ...

user output
1262932 289411 628862 1333008 ...
Truncated

Test 61

Verdict:

input
100000 132325 159285
17 66 72 14 70 37 21 77 77 8 1...

correct output
26997290 43133384 15738489 536...

user output
(empty)

Test 62

Verdict:

input
100000 112555 199720
66 40 4 62 93 18 87 17 93 33 6...

correct output
53634787 50 13386258 910 46 35...

user output
(empty)

Test 63

Verdict:

input
100000 115401 118508
58 46 99 47 45 48 88 55 65 26 ...

correct output
47323160 60674434 55 18495 444...

user output
(empty)

Test 64

Verdict:

input
100000 132622 107072
96 14 46 26 86 95 48 16 57 1 5...

correct output
41 78 72 597 54188145 69570768...

user output
(empty)

Test 65

Verdict:

input
100000 195060 190063
59 52 10 99 9 91 4 50 40 100 5...

correct output
44 77677116 54830906 64 35 593...

user output
(empty)

Test 66

Verdict:

input
100000 83300 105518
34 24 50 62 68 7 20 19 22 13 8...

correct output
57 28 34883032 1639 34687735 3...

user output
(empty)

Test 67

Verdict:

input
100000 183934 194749
75 4 99 29 11 14 93 62 73 75 9...

correct output
50631809 42390149 89 11 21 787...

user output
(empty)

Test 68

Verdict:

input
100000 61446 122734
15 89 30 58 78 27 21 34 61 79 ...

correct output
77 1070 59 79 55 7 2219 55 189...

user output
(empty)

Test 69

Verdict:

input
100000 181019 101111
34 4 19 66 4 58 51 92 60 8 30 ...

correct output
4469 29 24653966 1503 87861918...

user output
(empty)