CSES - Aalto Competitive Programming 2024 - wk7 - Wed

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

Submission details
Task:	Shallow waters
Sender:	aalto2024h_005
Submission time:	2024-10-23 17:30:02 +0300
Language:	C++ (C++11)
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.02 s	details
#33	ACCEPTED	0.01 s	details
#34	ACCEPTED	0.01 s	details
#35	ACCEPTED	0.02 s	details
#36	ACCEPTED	0.02 s	details
#37	ACCEPTED	0.02 s	details
#38	ACCEPTED	0.01 s	details
#39	ACCEPTED	0.02 s	details
#40	ACCEPTED	0.01 s	details
#41	ACCEPTED	0.01 s	details
#42	ACCEPTED	0.04 s	details
#43	ACCEPTED	0.07 s	details
#44	ACCEPTED	0.05 s	details
#45	ACCEPTED	0.04 s	details
#46	ACCEPTED	0.04 s	details
#47	ACCEPTED	0.06 s	details
#48	ACCEPTED	0.07 s	details
#49	ACCEPTED	0.07 s	details
#50	ACCEPTED	0.04 s	details
#51	ACCEPTED	0.06 s	details
#52	ACCEPTED	0.39 s	details
#53	ACCEPTED	0.48 s	details
#54	ACCEPTED	0.37 s	details
#55	ACCEPTED	0.51 s	details
#56	ACCEPTED	0.43 s	details
#57	ACCEPTED	0.36 s	details
#58	ACCEPTED	0.32 s	details
#59	ACCEPTED	0.43 s	details
#60	ACCEPTED	0.31 s	details
#61	ACCEPTED	0.34 s	details

Code

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

void floyd_warshall(vector<vector<long long>> &dist, long long n) {

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] < min(dist[i][k], dist[k][j]))
                    dist[i][j] = min(dist[i][k], dist[k][j]);
            }
        }
    }

}

/*
void flow_warshall_path_reconstruction(vector<vector<long long>> &w, vector<vector<long long>> &dist, int n, vector<vector<int>> &prev) {

	for (int u = 0; u < n; u++) {
		for (int v = 0; v < n; v++) {
			dist[u][v] = w[u][v];
			prev[u][v] = u;
		}
	}

	for (int v = 0; v < n; v++) {
		dist[v][v] = 0;
		prev[v][v] = v;
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dist[i][j] < min(dist[i][k], dist[k][j])) {
					dist[i][j] = min(dist[i][k], dist[k][j]);
					prev[i][j] = prev[k][j];
				}
			}
		}
	}

}

vector<int> make_path(int u, int v, vector<vector<int>> &prev, int n) {

	vector<int> path;

	if (prev[u][v] == -1)
		return path;
	
	path.push_back(v);

	while (u != v) {
		v = prev[u][v];
		path.push_back(v);
	}

	reverse(path.begin(), path.end());
	return path;

}*/

int main() {

    int n, q;
    cin >> n >> q;

    vector<vector<long long>> w(n, vector<long long>(n));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> w[i][j];
	}

	floyd_warshall(w, n);

	//vector<vector<long long>> dist(n, vector<long long>(n, 0));
	//vector<vector<int>> prev(n, vector<int>(n, -1));
	
	//flow_warshall_path_reconstruction(w, dist, n, prev);

	vector<pair<int, int>> queries(q);

	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		queries[i] = {a, b};
	}

	for (int i = 0; i < q; i++) {
		pair<int, int> p = queries[i];
		int a = p.first, b = p.second;

		cout << w[a][b] << endl;
	}

		/*vector<int> path = make_path(a, b, prev, n);

		if (path.size() == 0) continue;

		long long minimum = LONG_LONG_MAX;

		for (int i = 1; i < path.size(); i++)
			minimum = min(minimum, dist[path[i-1]][path[i]]);

		cout << minimum << endl;
	}*/

}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 0 39 39 0 1 2` view save

correct output
`39` view save

user output
`39` view save

Test 2

Verdict: ACCEPTED

input
`2 1 0 48 48 0 2 1` view save

correct output
`48` view save

user output
`48` view save

Test 3

Verdict: ACCEPTED

input
`3 2 0 69 81 69 0 60 81 60 0 1 3 ...` view save

correct output
`81 69` view save

user output
`81 69` view save

Test 4

Verdict: ACCEPTED

input
`3 1 0 41 45 41 0 64 45 64 0 1 2` view save

correct output
`45` view save

user output
`45` view save

Test 5

Verdict: ACCEPTED

input
`3 1 0 87 49 87 0 77 49 77 0 3 1` view save

correct output
`77` view save

user output
`77` view save

Test 6

Verdict: ACCEPTED

input
`3 3 0 56 38 56 0 7 38 7 0 1 2 ...` view save

correct output
`56 38 38` view save

user output
`56 38 38` view save

Test 7

Verdict: ACCEPTED

input
`4 2 0 88 79 73 88 0 56 85 79 56 0 30 73 85 30 0 ...` view save

correct output
`85 79` view save

user output
`85 79` view save

Test 8

Verdict: ACCEPTED

input
`4 1 0 54 20 63 54 0 100 37 20 100 0 33 63 37 33 0 ...` view save

correct output
`54` view save

user output
`54` view save

Test 9

Verdict: ACCEPTED

input
`4 6 0 77 96 6 77 0 92 52 96 92 0 37 6 52 37 0 ...` view save

correct output
`92 52 52 52 52 ...` view save

user output
`92 52 52 52 52 ...` view save

Test 10

Verdict: ACCEPTED

input
`4 2 0 41 12 88 41 0 57 61 12 57 0 77 88 61 77 0 ...` view save

correct output
`61 88` view save

user output
`61 88` view save

Test 11

Verdict: ACCEPTED

input
`4 5 0 58 68 17 58 0 11 87 68 11 0 57 17 87 57 0 ...` view save

correct output
`58 58 58 58 58` view save

user output
`58 58 58 58 58` view save

Test 12

Verdict: ACCEPTED

input
`5 4 0 86 65 6 80 86 0 39 97 82 65 39 0 28 53 6 97 28 0 48 ...` view save

correct output
`86 86 86 65` view save

user output
`86 86 86 65` view save

Test 13

Verdict: ACCEPTED

input
`5 5 0 13 10 67 42 13 0 40 40 32 10 40 0 94 69 67 40 94 0 53 ...` view save

correct output
`67 67 67 69 40` view save

user output
`67 67 67 69 40` view save

Test 14

Verdict: ACCEPTED

input
`5 5 0 95 34 12 63 95 0 16 30 82 34 16 0 49 53 12 30 49 0 69 ...` view save

correct output
`69 82 69 82 53` view save

user output
`69 82 69 82 53` view save

Test 15

Verdict: ACCEPTED

input
`5 3 0 13 90 25 3 13 0 2 6 15 90 2 0 10 46 25 6 10 0 46 ...` view save

correct output
`46 46 46` view save

user output
`46 46 46` view save

Test 16

Verdict: ACCEPTED

input
`5 4 0 86 22 70 78 86 0 15 26 1 22 15 0 91 20 70 26 91 0 58 ...` view save

correct output
`86 70 70 70` view save

user output
`86 70 70 70` view save

Test 17

Verdict: ACCEPTED

input
`5 3 0 37 62 49 9 37 0 40 30 65 62 40 0 100 74 49 30 100 0 82 ...` view save

correct output
`62 62 62` view save

user output
`62 62 62` view save

Test 18

Verdict: ACCEPTED

input
`5 3 0 7 60 54 44 7 0 10 34 76 60 10 0 49 74 54 34 49 0 39 ...` view save

correct output
`60 54 74` view save

user output
`60 54 74` view save

Test 19

Verdict: ACCEPTED

input
`5 4 0 98 54 42 68 98 0 27 27 87 54 27 0 2 81 42 27 2 0 34 ...` view save

correct output
`42 42 81 42` view save

user output
`42 42 81 42` view save

Test 20

Verdict: ACCEPTED

input
`5 5 0 38 2 41 56 38 0 62 53 15 2 62 0 88 55 41 53 88 0 71 ...` view save

correct output
`56 62 62 56 71` view save

user output
`56 62 62 56 71` view save

Test 21

Verdict: ACCEPTED

input
`5 8 0 1 22 14 17 1 0 88 9 32 22 88 0 40 88 14 9 40 0 38 ...` view save

correct output
`22 40 22 40 40 ...` view save

user output
`22 40 22 40 40 ...` view save

Test 22

Verdict: ACCEPTED

input
`10 26 0 65 80 9 98 64 27 62 36 68 65 0 82 65 48 59 19 15 62 18 80 82 0 3 80 15 78 62 44 22 9 65 3 0 81 54 74 23 91 36 ...` view save

correct output
`98 81 76 80 80 ...` view save

user output
`98 81 76 80 80 ...` view save

Test 23

Verdict: ACCEPTED

input
`10 1 0 10 42 68 81 90 10 32 99 45 10 0 32 92 72 83 60 15 67 47 42 32 0 42 97 9 43 69 75 91 68 92 42 0 81 83 68 79 30 10 ...` view save

correct output
`90` view save

user output
`90` view save

Test 24

Verdict: ACCEPTED

input
`10 25 0 34 63 79 51 60 47 39 97 43 34 0 82 26 30 57 37 62 51 81 63 82 0 86 7 23 21 80 51 44 79 26 86 0 29 23 47 100 22 36 ...` view save

correct output
`81 81 81 66 100 ...` view save

user output
`81 81 81 66 100 ...` view save

Test 25

Verdict: ACCEPTED

input
`10 10 0 90 3 60 29 79 98 10 41 87 90 0 15 92 31 82 15 42 57 67 3 15 0 3 70 31 68 66 47 59 60 92 3 0 59 26 33 79 75 88 ...` view save

correct output
`82 79 90 91 79 ...` view save

user output
`82 79 90 91 79 ...` view save

Test 26

Verdict: ACCEPTED

input
`10 41 0 22 78 60 44 8 53 55 40 51 22 0 1 82 2 7 88 22 64 47 78 1 0 1 95 61 94 53 63 69 60 82 1 0 4 18 84 19 23 36 ...` view save

correct output
`78 78 61 78 64 ...` view save

user output
`78 78 61 78 64 ...` Truncated

Test 27

Verdict: ACCEPTED

input
`10 35 0 62 9 28 60 15 3 58 26 47 62 0 65 21 74 90 48 37 73 58 9 65 0 42 27 17 21 1 81 99 28 21 42 0 2 96 69 70 67 7 ...` view save

correct output
`62 62 62 62 90 ...` view save

user output
`62 62 62 62 90 ...` Truncated

Test 28

Verdict: ACCEPTED

input
`10 35 0 60 44 100 6 55 72 72 75 38 60 0 76 92 68 58 47 80 39 74 44 76 0 82 72 13 100 94 73 71 100 92 82 0 15 9 55 89 47 25 ...` view save

correct output
`89 83 89 89 92 ...` view save

user output
`89 83 89 89 92 ...` Truncated

Test 29

Verdict: ACCEPTED

input
`10 20 0 54 68 91 61 14 21 84 46 72 54 0 87 70 26 45 49 45 55 42 68 87 0 22 96 53 50 77 36 42 91 70 22 0 86 39 62 96 32 99 ...` view save

correct output
`91 87 87 96 91 ...` view save

user output
`91 87 87 96 91 ...` view save

Test 30

Verdict: ACCEPTED

input
`10 9 0 2 56 43 7 23 3 32 7 80 2 0 15 36 30 54 34 15 65 23 56 15 0 29 99 40 36 44 61 99 43 36 29 0 68 95 28 12 14 57 ...` view save

correct output
`90 67 67 90 67 ...` view save

user output
`90 67 67 90 67 ...` view save

Test 31

Verdict: ACCEPTED

input
`10 30 0 22 17 58 39 81 65 88 62 19 22 0 32 14 63 84 21 80 44 93 17 32 0 90 70 99 87 91 50 69 58 14 90 0 57 11 93 5 60 40 ...` view save

correct output
`88 88 88 88 93 ...` view save

user output
`88 88 88 88 93 ...` view save

Test 32

Verdict: ACCEPTED

input
`100 4060 0 224279712 686036287 45105249...` view save

correct output
`984509996 986462105 982248996 984656610 985935261 ...` view save

user output
`984509996 986462105 982248996 984656610 985935261 ...` Truncated

Test 33

Verdict: ACCEPTED

input
`100 676 0 527822662 997975632 53018119...` view save

correct output
`993798769 991489320 988392606 975549477 986420088 ...` view save

user output
`993798769 991489320 988392606 975549477 986420088 ...` Truncated

Test 34

Verdict: ACCEPTED

input
`100 333 0 436234512 371770128 46427426...` view save

correct output
`973778856 973778856 975526572 973096824 972749112 ...` view save

user output
`973778856 973778856 975526572 973096824 972749112 ...` Truncated

Test 35

Verdict: ACCEPTED

input
`100 3357 0 68472304 913723608 220052402...` view save

correct output
`987176834 981901632 989344571 983084587 989344571 ...` view save

user output
`987176834 981901632 989344571 983084587 989344571 ...` Truncated

Test 36

Verdict: ACCEPTED

input
`100 3628 0 534502368 539714259 28374756...` view save

correct output
`986332762 993409969 993409969 984535136 986332762 ...` view save

user output
`986332762 993409969 993409969 984535136 986332762 ...` Truncated

Test 37

Verdict: ACCEPTED

input
`100 4615 0 509293538 258847661 53332274...` view save

correct output
`986084005 993410015 993410015 965516330 986242161 ...` view save

user output
`986084005 993410015 993410015 965516330 986242161 ...` Truncated

Test 38

Verdict: ACCEPTED

input
`100 2345 0 863913461 192636102 88476477...` view save

correct output
`985034014 984712168 970064352 985034014 983716327 ...` view save

user output
`985034014 984712168 970064352 985034014 983716327 ...` Truncated

Test 39

Verdict: ACCEPTED

input
`100 4167 0 278244915 816596895 99494306...` view save

correct output
`994650753 988169835 988586303 974999473 988169835 ...` view save

user output
`994650753 988169835 988586303 974999473 988169835 ...` Truncated

Test 40

Verdict: ACCEPTED

input
`100 2952 0 908068381 834928493 76958654...` view save

correct output
`971019561 990687292 981311675 986274515 994580228 ...` view save

user output
`971019561 990687292 981311675 986274515 994580228 ...` Truncated

Test 41

Verdict: ACCEPTED

input
`100 1620 0 257277309 280264417 59391568...` view save

correct output
`977276808 986699027 973703850 984814274 986229209 ...` view save

user output
`977276808 986699027 973703850 984814274 986229209 ...` Truncated

Test 42

Verdict: ACCEPTED

input
`200 455 0 686036287 971118925 48977720...` view save

correct output
`991763634 993383365 989047420 993694416 992916290 ...` view save

user output
`991763634 993383365 989047420 993694416 992916290 ...` Truncated

Test 43

Verdict: ACCEPTED

input
`200 12733 0 997975632 145040139 59548994...` view save

correct output
`992841688 994103522 994103522 993324323 993413618 ...` view save

user output
`992841688 994103522 994103522 993324323 993413618 ...` Truncated

Test 44

Verdict: ACCEPTED

input
`200 10671 0 371770128 104741444 35097588...` view save

correct output
`994112705 992684847 991175588 992684847 991850584 ...` view save

user output
`994112705 992684847 991175588 992684847 991850584 ...` Truncated

Test 45

Verdict: ACCEPTED

input
`200 785 0 913723608 846741138 23261249...` view save

correct output
`991015102 991393613 991393613 991393613 991393613 ...` view save

user output
`991015102 991393613 991393613 991393613 991393613 ...` Truncated

Test 46

Verdict: ACCEPTED

input
`200 4341 0 539714259 993409969 52728320...` view save

correct output
`995748996 992259426 995648041 995748996 995748996 ...` view save

user output
`995748996 992259426 995648041 995748996 995748996 ...` Truncated

Test 47

Verdict: ACCEPTED

input
`200 10033 0 258847661 29756805 772449744...` view save

correct output
`994518775 994534294 994518775 974715985 990234431 ...` view save

user output
`994518775 994534294 994518775 974715985 990234431 ...` Truncated

Test 48

Verdict: ACCEPTED

input
`200 19576 0 192636102 43478262 277317100...` view save

correct output
`990666123 991249036 990616659 991249036 991249036 ...` view save

user output
`990666123 991249036 990616659 991249036 991249036 ...` Truncated

Test 49

Verdict: ACCEPTED

input
`200 17516 0 816596895 223011120 40179408...` view save

correct output
`989788855 989788855 989788855 989788855 989788855 ...` view save

user output
`989788855 989788855 989788855 989788855 989788855 ...` Truncated

Test 50

Verdict: ACCEPTED

input
`200 2236 0 834928493 789779330 75492200...` view save

correct output
`990202245 990881031 993287512 993287512 996688854 ...` view save

user output
`990202245 990881031 993287512 993287512 996688854 ...` Truncated

Test 51

Verdict: ACCEPTED

input
`200 13669 0 280264417 35137122 58869367 ...` view save

correct output
`985495492 987275634 987275634 987275634 987275634 ...` view save

user output
`985495492 987275634 987275634 987275634 987275634 ...` Truncated

Test 52

Verdict: ACCEPTED

input
`500 44127 0 623250361 488402074 93887976...` view save

correct output
`997518315 997518315 997518315 997518315 997247172 ...` view save

user output
`997518315 997518315 997518315 997518315 997247172 ...` Truncated

Test 53

Verdict: ACCEPTED

input
`500 89310 0 410279705 670881494 19798128...` view save

correct output
`994290020 994290020 994290020 994290020 994290020 ...` view save

user output
`994290020 994290020 994290020 994290020 994290020 ...` Truncated

Test 54

Verdict: ACCEPTED

input
`500 32068 0 556762013 260875339 89984504...` view save

correct output
`996936245 996567301 996936245 996936245 996393864 ...` view save

user output
`996936245 996567301 996936245 996936245 996393864 ...` Truncated

Test 55

Verdict: ACCEPTED

input
`500 81911 0 365429213 243439455 38401914...` view save

correct output
`996657976 995517614 996657976 996419449 996657976 ...` view save

user output
`996657976 995517614 996657976 996419449 996657976 ...` Truncated

Test 56

Verdict: ACCEPTED

input
`500 66557 0 736625865 907021066 67376384...` view save

correct output
`996250418 996250418 996250418 996250418 996250418 ...` view save

user output
`996250418 996250418 996250418 996250418 996250418 ...` Truncated

Test 57

Verdict: ACCEPTED

input
`500 28215 0 507642456 772882187 23298617...` view save

correct output
`996927836 995199945 988550843 996861124 996927836 ...` view save

user output
`996927836 995199945 988550843 996861124 996927836 ...` Truncated

Test 58

Verdict: ACCEPTED

input
`500 4722 0 681246594 433718444 81827072...` view save

correct output
`996596738 995772851 996596738 995904634 994249067 ...` view save

user output
`996596738 995772851 996596738 995904634 994249067 ...` Truncated

Test 59

Verdict: ACCEPTED

input
`500 66897 0 670154826 911171975 19319438...` view save

correct output
`997410816 997103192 997322209 997322209 997410816 ...` view save

user output
`997410816 997103192 997322209 997322209 997410816 ...` Truncated

Test 60

Verdict: ACCEPTED

input
`500 4171 0 998224343 144467837 75333130...` view save

correct output
`997492638 996317859 993722528 996341116 997492638 ...` view save

user output
`997492638 996317859 993722528 996341116 997492638 ...` Truncated

Test 61

Verdict: ACCEPTED

input
`500 18979 0 722938317 668705452 11233444...` view save

correct output
`997573682 994464545 996219897 997093906 997573682 ...` view save

user output
`997573682 994464545 996219897 997093906 997573682 ...` Truncated

Aalto Competitive Programming 2024 - wk7 - Wed

Shallow waters

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

Tasks

Submissions (aalto2024h_005)