CSES - Aalto Competitive Programming 2024 - wk4 - Wed

CSES - Aalto Competitive Programming 2024 - wk4 - Wed - Results

Submission details
Task:	Conurbation
Sender:	aalto2024d_002
Submission time:	2024-09-25 17:12:38 +0300
Language:	C++ (C++17)
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.00 s	details
#3	ACCEPTED	0.00 s	details
#4	ACCEPTED	0.00 s	details
#5	ACCEPTED	0.00 s	details
#6	ACCEPTED	0.00 s	details
#7	ACCEPTED	0.00 s	details
#8	ACCEPTED	0.00 s	details
#9	ACCEPTED	0.00 s	details
#10	ACCEPTED	0.00 s	details
#11	ACCEPTED	0.00 s	details
#12	ACCEPTED	0.00 s	details
#13	ACCEPTED	0.00 s	details
#14	ACCEPTED	0.00 s	details
#15	ACCEPTED	0.00 s	details
#16	ACCEPTED	0.00 s	details
#17	ACCEPTED	0.00 s	details
#18	ACCEPTED	0.00 s	details
#19	ACCEPTED	0.00 s	details
#20	ACCEPTED	0.00 s	details
#21	ACCEPTED	0.00 s	details
#22	ACCEPTED	0.00 s	details
#23	ACCEPTED	0.00 s	details
#24	ACCEPTED	0.00 s	details
#25	ACCEPTED	0.00 s	details
#26	ACCEPTED	0.00 s	details
#27	ACCEPTED	0.00 s	details
#28	ACCEPTED	0.00 s	details
#29	ACCEPTED	0.00 s	details
#30	ACCEPTED	0.00 s	details
#31	ACCEPTED	0.00 s	details
#32	ACCEPTED	0.00 s	details
#33	ACCEPTED	0.01 s	details
#34	ACCEPTED	0.00 s	details
#35	ACCEPTED	0.00 s	details
#36	ACCEPTED	0.00 s	details
#37	ACCEPTED	0.00 s	details
#38	ACCEPTED	0.01 s	details
#39	ACCEPTED	0.00 s	details
#40	ACCEPTED	0.00 s	details
#41	ACCEPTED	0.00 s	details
#42	ACCEPTED	0.01 s	details
#43	ACCEPTED	0.01 s	details
#44	ACCEPTED	0.01 s	details
#45	ACCEPTED	0.01 s	details
#46	ACCEPTED	0.01 s	details
#47	ACCEPTED	0.01 s	details
#48	ACCEPTED	0.01 s	details
#49	ACCEPTED	0.01 s	details
#50	ACCEPTED	0.01 s	details
#51	ACCEPTED	0.00 s	details
#52	ACCEPTED	0.01 s	details
#53	ACCEPTED	0.01 s	details
#54	ACCEPTED	0.01 s	details
#55	ACCEPTED	0.01 s	details
#56	ACCEPTED	0.01 s	details
#57	ACCEPTED	0.01 s	details
#58	ACCEPTED	0.01 s	details
#59	ACCEPTED	0.01 s	details
#60	ACCEPTED	0.01 s	details
#61	ACCEPTED	0.28 s	details
#62	ACCEPTED	0.30 s	details
#63	ACCEPTED	0.23 s	details
#64	ACCEPTED	0.23 s	details
#65	ACCEPTED	0.36 s	details
#66	ACCEPTED	0.19 s	details
#67	ACCEPTED	0.36 s	details
#68	ACCEPTED	0.18 s	details
#69	ACCEPTED	0.27 s	details

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5+1;

int L[N], S[N];

void init() {
  for (int i = 0; i < N; ++i) L[i] = i;
  for (int i = 0; i < N; ++i) S[i] = 1;
}
int id(int i) {
  while (L[i] != i) i = L[i];
  return i;
}
int merge(int a, int b) {
  a = id(a);
  b = id(b);
  if (S[a] > S[b]) swap(a,b);
  S[b] += S[a];
  L[a] = b;
	return b;
}

int n, m, q;
ll T[N], ANS[N*2];
tuple<int,int,int> H[N*2];
tuple<int,int,int> Q[N*2];

int main() {
  init();
  cin >> n >> m >> q;
  for (int i = 0; i < n; ++i) {
    cin >> T[i];
  }
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		H[i] = {a-1,b-1,c};
	}
	for (int i = 0; i < q; ++i) {
		int a, b;
		cin >> a >> b;
		Q[i] = {b-1,a-1,i};
	}
	sort(Q,Q+q);
	int y = 0;
	for (int i = 0; i < q; ++i) {
		auto [b,a,j] = Q[i];
		while (y <= b && y < m) {
			auto [a0,b0,c0] = H[y++];
			a0 = id(a0); b0 = id(b0);
			if (a0 == b0) {
				T[a0] += c0;
				continue;
			}
			ll sum = T[a0] + T[b0] + c0;
			int id0 = merge(a0,b0);
			T[id0] = sum;
		}
		ANS[j] = T[id(a)];
	}
	for (int i = 0; i < q; ++i) {
		cout << ANS[i] << ' ';
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 3 6 10 1 2 6 1 1 2 1 ...` view save

correct output
`22 22 22` view save

user output
`22 22 22` view save

Test 2

Verdict: ACCEPTED

input
`2 1 3 5 3 1 2 9 2 1 2 1 ...` view save

correct output
`17 17 17` view save

user output
`17 17 17` view save

Test 3

Verdict: ACCEPTED

input
`2 1 4 1 4 1 2 7 1 1 2 1 ...` view save

correct output
`12 12 12 12` view save

user output
`12 12 12 12` view save

Test 4

Verdict: ACCEPTED

input
`3 1 8 6 5 1 1 2 10 3 1 2 1 ...` view save

correct output
`1 21 21 1 21 1 21 1` view save

user output
`1 21 21 1 21 1 21 1` view save

Test 5

Verdict: ACCEPTED

input
`3 2 7 3 10 8 1 2 8 1 3 7 2 2 ...` view save

correct output
`36 21 21 8 21 36 36` view save

user output
`36 21 21 8 21 36 36` view save

Test 6

Verdict: ACCEPTED

input
`3 3 5 9 6 2 1 2 1 1 3 5 2 3 9 ...` view save

correct output
`16 2 23 32 32` view save

user output
`16 2 23 32 32` view save

Test 7

Verdict: ACCEPTED

input
`3 1 4 10 6 2 1 2 5 2 1 2 1 ...` view save

correct output
`21 21 21 21` view save

user output
`21 21 21 21` view save

Test 8

Verdict: ACCEPTED

input
`4 6 8 2 3 1 1 1 2 5 1 3 1 1 4 9 ...` view save

correct output
`34 34 1 1 1 22 25 37` view save

user output
`34 34 1 1 1 22 25 37` view save

Test 9

Verdict: ACCEPTED

input
`4 4 11 7 9 4 9 1 4 9 2 3 8 2 4 1 ...` view save

correct output
`9 25 25 56 25 25 25 25 56 4 4` view save

user output
`9 25 25 56 25 25 25 25 56 4 4` view save

Test 10

Verdict: ACCEPTED

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

correct output
`58 60 25 58 60` view save

user output
`58 60 25 58 60` view save

Test 11

Verdict: ACCEPTED

input
`4 4 7 6 6 9 8 1 3 1 1 4 1 2 3 5 ...` view save

correct output
`25 16 44 36 6 44 36` view save

user output
`25 16 44 36 6 44 36` view save

Test 12

Verdict: ACCEPTED

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

correct output
`50 74 9 69 4 82 9 41 4 74 9 50...` view save

user output
`50 74 9 69 4 82 9 41 4 74 9 50...` view save

Test 13

Verdict: ACCEPTED

input
`5 10 12 6 9 9 9 9 1 2 1 1 3 9 1 4 1 ...` view save

correct output
`68 58 34 44 34 75 58 16 68 68 ...` view save

user output
`68 58 34 44 34 75 58 16 68 68 ...` view save

Test 14

Verdict: ACCEPTED

input
`5 3 5 7 7 9 6 7 1 2 2 2 3 5 3 5 6 ...` view save

correct output
`9 6 43 30 43` view save

user output
`9 6 43 30 43` view save

Test 15

Verdict: ACCEPTED

input
`5 2 12 6 9 5 9 1 1 3 2 2 5 1 2 1 ...` view save

correct output
`9 13 13 13 13 9 9 9 13 13 13 9...` view save

user output
`9 13 13 13 13 9 9 9 13 13 13 9...` view save

Test 16

Verdict: ACCEPTED

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

correct output
`1 58 71 44 69 58 44 71 44 69 6...` view save

user output
`1 58 71 44 69 58 44 71 44 69 6...` view save

Test 17

Verdict: ACCEPTED

input
`5 2 14 1 7 4 8 4 2 5 6 3 5 5 2 2 ...` view save

correct output
`26 1 1 8 4 1 17 17 4 26 8 4 26...` view save

user output
`26 1 1 8 4 1 17 17 4 26 8 4 26...` view save

Test 18

Verdict: ACCEPTED

input
`5 10 8 7 8 5 6 6 1 2 2 1 3 1 1 4 10 ...` view save

correct output
`56 68 68 68 68 76 76 48` view save

user output
`56 68 68 68 68 76 76 48` view save

Test 19

Verdict: ACCEPTED

input
`5 4 13 6 7 9 9 4 1 3 4 2 3 4 3 5 1 ...` view save

correct output
`35 35 30 51 4 51 9 51 7 51 51 ...` view save

user output
`35 35 30 51 4 51 9 51 7 51 51 ...` view save

Test 20

Verdict: ACCEPTED

input
`5 2 15 9 3 5 1 7 2 3 5 2 5 8 3 1 ...` view save

correct output
`13 28 28 13 28 1 1 1 13 13 28 ...` view save

user output
`13 28 28 13 28 1 1 1 13 13 28 ...` view save

Test 21

Verdict: ACCEPTED

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

correct output
`61 2 61 67 49 67 67 67 26 49` view save

user output
`61 2 61 67 49 67 67 67 26 49` view save

Test 22

Verdict: ACCEPTED

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

correct output
`9 8 8 95 8 101 8 101 150 121 9...` view save

user output
`9 8 8 95 8 101 8 101 150 121 9...` view save

Test 23

Verdict: ACCEPTED

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

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

user output
`71 6 4 117 54 71 99 4 112 24 1...` view save

Test 24

Verdict: ACCEPTED

input
`10 7 10 6 2 8 8 3 9 6 5 5 9 2 3 2 2 7 1 3 5 10 ...` view save

correct output
`3 6 47 47 19 65 59 8 32 47` view save

user output
`3 6 47 47 19 65 59 8 32 47` view save

Test 25

Verdict: ACCEPTED

input
`10 6 24 3 1 1 5 7 1 2 5 5 7 1 2 3 1 3 3 2 6 4 ...` view save

correct output
`7 5 7 7 1 5 16 1 7 5 5 11 5 5 ...` view save

user output
`7 5 7 7 1 5 16 1 7 5 5 11 5 5 ...` view save

Test 26

Verdict: ACCEPTED

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

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

user output
`1 104 117 2 38 111 1 107 91 26...` view save

Test 27

Verdict: ACCEPTED

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

correct output
`7 17 10 17 22 2 2 5 5 17 35 6 ...` view save

user output
`7 17 10 17 22 2 2 5 5 17 35 6 ...` view save

Test 28

Verdict: ACCEPTED

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

correct output
`132 120 164 9 120 172 172 90 4...` view save

user output
`132 120 164 9 120 172 172 90 4...` view save

Test 29

Verdict: ACCEPTED

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

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

user output
`3 85 7 9 85 10 51 81 71 9 9 41...` view save

Test 30

Verdict: ACCEPTED

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

correct output
`20 25 8 5 25 20 8 6 5 20 25 20...` view save

user output
`20 25 8 5 25 20 8 6 5 20 25 20...` view save

Test 31

Verdict: ACCEPTED

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

correct output
`110 130 30 76 130 89 110 130 8...` view save

user output
`110 130 30 76 130 89 110 130 8...` view save

Test 32

Verdict: ACCEPTED

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

correct output
`60969 25642 39518 11438 50148 ...` view save

user output
`60969 25642 39518 11438 50148 ...` Truncated

Test 33

Verdict: ACCEPTED

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

correct output
`46 77 76 68840 2 10 53 10 1355...` view save

user output
`46 77 76 68840 2 10 53 10 1355...` Truncated

Test 34

Verdict: ACCEPTED

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

correct output
`32922 36267 13295 4921 25077 5...` view save

user output
`32922 36267 13295 4921 25077 5...` Truncated

Test 35

Verdict: ACCEPTED

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

correct output
`896 38 38016 75 929 55318 5531...` view save

user output
`896 38 38016 75 929 55318 5531...` Truncated

Test 36

Verdict: ACCEPTED

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

correct output
`77560 25 83317 35 47239 42343 ...` view save

user output
`77560 25 83317 35 47239 42343 ...` Truncated

Test 37

Verdict: ACCEPTED

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

correct output
`25 41638 83 11 578 35 37057 51...` view save

user output
`25 41638 83 11 578 35 37057 51...` Truncated

Test 38

Verdict: ACCEPTED

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

correct output
`33 111825 139106 48081 95088 7...` view save

user output
`33 111825 139106 48081 95088 7...` Truncated

Test 39

Verdict: ACCEPTED

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

correct output
`1003 2691 46 54 45 85 1996 385...` view save

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

Test 40

Verdict: ACCEPTED

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

correct output
`94382 66968 26853 65546 61406 ...` view save

user output
`94382 66968 26853 65546 61406 ...` Truncated

Test 41

Verdict: ACCEPTED

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

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

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

Test 42

Verdict: ACCEPTED

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

correct output
`7 131256 124647 183516 133600 ...` view save

user output
`7 131256 124647 183516 133600 ...` Truncated

Test 43

Verdict: ACCEPTED

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

correct output
`101488 71 87 16319 31 100814 8...` view save

user output
`101488 71 87 16319 31 100814 8...` Truncated

Test 44

Verdict: ACCEPTED

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

correct output
`128489 72606 464 145651 6 1079...` view save

user output
`128489 72606 464 145651 6 1079...` Truncated

Test 45

Verdict: ACCEPTED

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

correct output
`161772 9 172295 112826 77 1522...` view save

user output
`161772 9 172295 112826 77 1522...` Truncated

Test 46

Verdict: ACCEPTED

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

correct output
`71 118148 217768 55 89638 1898...` view save

user output
`71 118148 217768 55 89638 1898...` Truncated

Test 47

Verdict: ACCEPTED

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

correct output
`20 60 83 101039 109091 2 1818 ...` view save

user output
`20 60 83 101039 109091 2 1818 ...` Truncated

Test 48

Verdict: ACCEPTED

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

correct output
`84 114794 252841 255378 279356...` view save

user output
`84 114794 252841 255378 279356...` Truncated

Test 49

Verdict: ACCEPTED

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

correct output
`25 54 26334 60 67 45 3437 991 ...` view save

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

Test 50

Verdict: ACCEPTED

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

correct output
`272553 159000 231656 124672 79...` view save

user output
`272553 159000 231656 124672 79...` Truncated

Test 51

Verdict: ACCEPTED

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

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

user output
`98 93 91 470 37 3 17 1141 15 1...` Truncated

Test 52

Verdict: ACCEPTED

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

correct output
`213572 583269 845186 159953 87...` view save

user output
`213572 583269 845186 159953 87...` Truncated

Test 53

Verdict: ACCEPTED

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

correct output
`195264 59 1415 799110 64 15852...` view save

user output
`195264 59 1415 799110 64 15852...` Truncated

Test 54

Verdict: ACCEPTED

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

correct output
`31 65 701570 560095 388274 16 ...` view save

user output
`31 65 701570 560095 388274 16 ...` Truncated

Test 55

Verdict: ACCEPTED

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

correct output
`495761 78 455001 722437 81 371...` view save

user output
`495761 78 455001 722437 81 371...` Truncated

Test 56

Verdict: ACCEPTED

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

correct output
`1147264 289548 798155 824295 4...` view save

user output
`1147264 289548 798155 824295 4...` Truncated

Test 57

Verdict: ACCEPTED

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

correct output
`86 46 70 400514 48 462515 96 2...` view save

user output
`86 46 70 400514 48 462515 96 2...` Truncated

Test 58

Verdict: ACCEPTED

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

correct output
`626156 300086 1144633 117105 1...` view save

user output
`626156 300086 1144633 117105 1...` Truncated

Test 59

Verdict: ACCEPTED

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

correct output
`335 52 85 54 2458 1476 252478 ...` view save

user output
`335 52 85 54 2458 1476 252478 ...` Truncated

Test 60

Verdict: ACCEPTED

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

correct output
`1263182 290251 628913 1333935 ...` view save

user output
`1263182 290251 628913 1333935 ...` Truncated

Test 61

Verdict: ACCEPTED

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

correct output
`26997290 43133384 15738489 536...` view save

user output
`26997290 43133384 15738489 536...` Truncated

Test 62

Verdict: ACCEPTED

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

correct output
`53634787 50 13386258 910 46 35...` view save

user output
`53634787 50 13386258 910 46 35...` Truncated

Test 63

Verdict: ACCEPTED

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

correct output
`47323160 60674434 55 18495 444...` view save

user output
`47323160 60674434 55 18495 444...` Truncated

Test 64

Verdict: ACCEPTED

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

correct output
`41 78 72 597 54188145 69570768...` view save

user output
`41 78 72 597 54188145 69570768...` Truncated

Test 65

Verdict: ACCEPTED

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

correct output
`44 77677116 54830906 64 35 593...` view save

user output
`44 77677116 54830906 64 35 593...` Truncated

Test 66

Verdict: ACCEPTED

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

correct output
`57 28 34883032 1639 34687735 3...` view save

user output
`57 28 34883032 1639 34687735 3...` Truncated

Test 67

Verdict: ACCEPTED

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

correct output
`50631809 42390149 89 11 21 787...` view save

user output
`50631809 42390149 89 11 21 787...` Truncated

Test 68

Verdict: ACCEPTED

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

correct output
`77 1070 59 79 55 7 2219 55 189...` view save

user output
`77 1070 59 79 55 7 2219 55 189...` Truncated

Test 69

Verdict: ACCEPTED

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

correct output
`4469 29 24653966 1503 87861918...` view save

user output
`4469 29 24653966 1503 87861918...` Truncated

Aalto Competitive Programming 2024 - wk4 - Wed

Conurbation

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Test 65

Test 66

Test 67

Test 68

Test 69

Tasks

Submissions (aalto2024d_002)