CSES - Aalto Competitive Programming 2024 - wk6 - Mon

CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Results

Submission details
Task:	Wide delivery
Sender:	laluj
Submission time:	2024-10-07 17:04:36 +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.00 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.00 s	details
#39	ACCEPTED	0.00 s	details
#40	ACCEPTED	0.00 s	details
#41	ACCEPTED	0.00 s	details
#42	ACCEPTED	0.00 s	details
#43	ACCEPTED	0.00 s	details
#44	ACCEPTED	0.01 s	details
#45	ACCEPTED	0.00 s	details
#46	ACCEPTED	0.01 s	details
#47	ACCEPTED	0.00 s	details
#48	ACCEPTED	0.01 s	details
#49	ACCEPTED	0.00 s	details
#50	ACCEPTED	0.01 s	details
#51	ACCEPTED	0.01 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.27 s	details
#61	ACCEPTED	0.24 s	details
#62	ACCEPTED	0.25 s	details
#63	ACCEPTED	0.27 s	details
#64	ACCEPTED	0.35 s	details
#65	ACCEPTED	0.22 s	details
#66	ACCEPTED	0.33 s	details
#67	ACCEPTED	0.19 s	details
#68	ACCEPTED	0.33 s	details
#69	ACCEPTED	0.17 s	details

Code

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << ": " << x << endl;
#define ll long long
#define ull unsigned long long
#define vi vector<int>

struct route {
    ll dest;
    ll width;
};

int main() {
    int n,m;
    cin >> n >> m;
    
    vector<vector<route>> routes (n+1);
    ll a, b, c;
    for (ll i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        routes[a].push_back({b,c});
        routes[b].push_back({a,c});
    }

    // DIJKSTRA ALGORITHM
    vector<bool> processed (n+1, false);
    vector<ll>  maxwidth (n+1, 0); maxwidth[1] = LONG_LONG_MAX;
    priority_queue<pair<ll,ll>> q;
    q.push({LONG_LONG_MAX,1});
    while (q.empty() == false) {
        a = q.top().second; q.pop();
        if (processed[a]) continue;
        processed[a] = true;
        for (route& r : routes[a]) {
            if (min(maxwidth[a], r.width) > maxwidth[r.dest]) {
                maxwidth[r.dest] = min(maxwidth[a], r.width);
                q.push({maxwidth[r.dest], r.dest});
            }
        }
    }

    for (ll i = 2; i <= n; i++)
    {
        cout << maxwidth[i] << ' ';
    }
    cout << endl;    

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 1 2 10` view save

correct output
`10` view save

user output
`10` view save

Test 2

Verdict: ACCEPTED

input
`3 2 1 3 2 2 3 3` view save

correct output
`2 2` view save

user output
`2 2` view save

Test 3

Verdict: ACCEPTED

input
`3 2 1 2 7 2 3 9` view save

correct output
`7 7` view save

user output
`7 7` view save

Test 4

Verdict: ACCEPTED

input
`3 2 1 2 7 1 3 5` view save

correct output
`7 5` view save

user output
`7 5` view save

Test 5

Verdict: ACCEPTED

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

correct output
`1 5` view save

user output
`1 5` view save

Test 6

Verdict: ACCEPTED

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

correct output
`6 6 7` view save

user output
`6 6 7` view save

Test 7

Verdict: ACCEPTED

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

correct output
`10 4 7` view save

user output
`10 4 7` view save

Test 8

Verdict: ACCEPTED

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

correct output
`5 3 3` view save

user output
`5 3 3` view save

Test 9

Verdict: ACCEPTED

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

correct output
`5 3 3` view save

user output
`5 3 3` view save

Test 10

Verdict: ACCEPTED

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

correct output
`7 7 7 7` view save

user output
`7 7 7 7` view save

Test 11

Verdict: ACCEPTED

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

correct output
`9 9 10 9` view save

user output
`9 9 10 9` view save

Test 12

Verdict: ACCEPTED

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

correct output
`5 5 4 5` view save

user output
`5 5 4 5` view save

Test 13

Verdict: ACCEPTED

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

correct output
`3 2 2 3` view save

user output
`3 2 2 3` view save

Test 14

Verdict: ACCEPTED

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

correct output
`3 3 3 3` view save

user output
`3 3 3 3` view save

Test 15

Verdict: ACCEPTED

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

correct output
`3 3 3 3` view save

user output
`3 3 3 3` view save

Test 16

Verdict: ACCEPTED

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

correct output
`8 8 9 8` view save

user output
`8 8 9 8` view save

Test 17

Verdict: ACCEPTED

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

correct output
`8 6 4 8` view save

user output
`8 6 4 8` view save

Test 18

Verdict: ACCEPTED

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

correct output
`6 9 6 4` view save

user output
`6 9 6 4` view save

Test 19

Verdict: ACCEPTED

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

correct output
`4 8 9 4` view save

user output
`4 8 9 4` view save

Test 20

Verdict: ACCEPTED

input
`10 30 1 2 2 1 4 7 1 7 3 1 9 7 ...` view save

correct output
`7 7 7 7 7 7 7 7 7` view save

user output
`7 7 7 7 7 7 7 7 7` view save

Test 21

Verdict: ACCEPTED

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

correct output
`9 10 10 8 9 9 9 9 9` view save

user output
`9 10 10 8 9 9 9 9 9` view save

Test 22

Verdict: ACCEPTED

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

correct output
`6 5 1 5 6 5 2 5 1` view save

user output
`6 5 1 5 6 5 2 5 1` view save

Test 23

Verdict: ACCEPTED

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

correct output
`1 1 1 1 1 1 2 1 1` view save

user output
`1 1 1 1 1 1 2 1 1` view save

Test 24

Verdict: ACCEPTED

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

correct output
`10 10 10 9 10 10 10 8 10` view save

user output
`10 10 10 9 10 10 10 8 10` view save

Test 25

Verdict: ACCEPTED

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

correct output
`3 4 5 3 3 6 5 6 3` view save

user output
`3 4 5 3 3 6 5 6 3` view save

Test 26

Verdict: ACCEPTED

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

correct output
`9 8 9 10 9 9 9 9 9` view save

user output
`9 8 9 10 9 9 9 9 9` view save

Test 27

Verdict: ACCEPTED

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

correct output
`6 8 7 7 7 8 6 4 10` view save

user output
`6 8 7 7 7 8 6 4 10` view save

Test 28

Verdict: ACCEPTED

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

correct output
`1 1 3 3 3 9 3 3 3` view save

user output
`1 1 3 3 3 9 3 3 3` view save

Test 29

Verdict: ACCEPTED

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

correct output
`9 9 9 9 10 10 9 9 10` view save

user output
`9 9 9 9 10 10 9 9 10` view save

Test 30

Verdict: ACCEPTED

input
`100 319 1 37 596623826 1 67 998074506 1 68 9921450 1 71 719317411 ...` view save

correct output
`809139202 779101021 809139202 ...` view save

user output
`809139202 779101021 809139202 ...` Truncated

Test 31

Verdict: ACCEPTED

input
`100 266 1 23 218517540 1 24 983124839 1 31 8592846 1 89 688876470 ...` view save

correct output
`847611626 667780838 619621653 ...` view save

user output
`847611626 667780838 619621653 ...` Truncated

Test 32

Verdict: ACCEPTED

input
`100 274 1 16 840345805 1 19 904448220 1 38 716537090 1 48 994458105 ...` view save

correct output
`689140135 768509869 779139365 ...` view save

user output
`689140135 768509869 779139365 ...` Truncated

Test 33

Verdict: ACCEPTED

input
`100 320 1 2 662868746 1 13 500034126 1 18 920268074 1 28 358826234 ...` view save

correct output
`718105196 718105196 718105196 ...` view save

user output
`718105196 718105196 718105196 ...` Truncated

Test 34

Verdict: ACCEPTED

input
`100 487 1 6 372811120 1 12 326784229 1 62 767189702 1 63 813226706 ...` view save

correct output
`827543856 832678805 832678805 ...` view save

user output
`827543856 832678805 832678805 ...` Truncated

Test 35

Verdict: ACCEPTED

input
`100 188 1 26 137494118 1 37 131337951 1 41 826708914 1 70 649947068 ...` view save

correct output
`649947068 640735040 649947068 ...` view save

user output
`649947068 640735040 649947068 ...` Truncated

Test 36

Verdict: ACCEPTED

input
`100 457 1 7 326353330 1 14 910706862 1 16 631528656 1 22 681300057 ...` view save

correct output
`820829965 702130526 896049001 ...` view save

user output
`820829965 702130526 896049001 ...` Truncated

Test 37

Verdict: ACCEPTED

input
`100 129 1 38 471910939 1 41 761706427 1 78 839382115 2 3 563011796 ...` view save

correct output
`507939807 507939807 507939807 ...` view save

user output
`507939807 507939807 507939807 ...` Truncated

Test 38

Verdict: ACCEPTED

input
`100 450 1 12 923504277 1 26 536204827 1 34 975212858 1 40 448475892 ...` view save

correct output
`875938306 871669886 869664776 ...` view save

user output
`875938306 871669886 869664776 ...` Truncated

Test 39

Verdict: ACCEPTED

input
`100 103 1 56 527185407 1 74 697438766 2 31 224913296 2 54 924311238 ...` view save

correct output
`37347058 37347058 8745675 3734...` view save

user output
`37347058 37347058 8745675 3734...` Truncated

Test 40

Verdict: ACCEPTED

input
`200 639 1 68 550240781 1 74 374173245 1 117 548283610 1 128 794673670 ...` view save

correct output
`717510768 717510768 717510768 ...` view save

user output
`717510768 717510768 717510768 ...` Truncated

Test 41

Verdict: ACCEPTED

input
`200 533 1 61 325205605 1 65 319257144 1 116 525067592 1 124 29641733 ...` view save

correct output
`637193247 637193247 637193247 ...` view save

user output
`637193247 637193247 637193247 ...` Truncated

Test 42

Verdict: ACCEPTED

input
`200 548 1 19 327701857 1 111 865795841 1 124 520305720 1 126 36803011 ...` view save

correct output
`614189792 727936226 716643678 ...` view save

user output
`614189792 727936226 716643678 ...` Truncated

Test 43

Verdict: ACCEPTED

input
`200 640 1 3 435247294 1 56 85483517 1 67 895163010 1 117 900338510 ...` view save

correct output
`766582321 702388421 749350380 ...` view save

user output
`766582321 702388421 749350380 ...` Truncated

Test 44

Verdict: ACCEPTED

input
`200 974 1 12 787274018 1 24 668226402 1 37 916647978 1 60 654136658 ...` view save

correct output
`766542739 853023687 809142552 ...` view save

user output
`766542739 853023687 809142552 ...` Truncated

Test 45

Verdict: ACCEPTED

input
`200 377 1 75 609995697 1 133 644237757 1 159 703362524 2 86 532732048 ...` view save

correct output
`532732048 613334611 703362524 ...` view save

user output
`532732048 613334611 703362524 ...` Truncated

Test 46

Verdict: ACCEPTED

input
`200 915 1 41 304105798 1 43 990074041 1 44 323946311 1 82 686995848 ...` view save

correct output
`878680360 818270725 878680360 ...` view save

user output
`878680360 818270725 878680360 ...` Truncated

Test 47

Verdict: ACCEPTED

input
`200 260 1 50 433414357 1 82 889544848 1 146 629986792 2 3 199714786 ...` view save

correct output
`260814459 247423049 458545197 ...` view save

user output
`260814459 247423049 458545197 ...` Truncated

Test 48

Verdict: ACCEPTED

input
`200 899 1 12 792915326 1 30 38447351 1 52 548163329 1 58 605992493 ...` view save

correct output
`839528481 701642263 839528481 ...` view save

user output
`839528481 701642263 839528481 ...` Truncated

Test 49

Verdict: ACCEPTED

input
`200 207 1 139 75253797 1 186 378941690 2 31 682441131 2 193 520226255 ...` view save

correct output
`76471569 76471569 24553207 245...` view save

user output
`76471569 76471569 24553207 245...` Truncated

Test 50

Verdict: ACCEPTED

input
`1000 3195 1 31 992737593 1 101 443344367 1 145 880813289 1 218 632539546 ...` view save

correct output
`708044511 801259894 665475214 ...` view save

user output
`708044511 801259894 665475214 ...` Truncated

Test 51

Verdict: ACCEPTED

input
`1000 2667 1 142 559482382 1 290 288767892 1 303 701355423 1 523 235314604 ...` view save

correct output
`665661624 483591462 665661624 ...` view save

user output
`665661624 483591462 665661624 ...` Truncated

Test 52

Verdict: ACCEPTED

input
`1000 2743 1 13 406970444 1 265 434163074 1 507 790586661 1 543 122643984 ...` view save

correct output
`601182566 390173081 730820742 ...` view save

user output
`601182566 390173081 730820742 ...` Truncated

Test 53

Verdict: ACCEPTED

input
`1000 3203 1 48 328382050 1 262 604204040 1 408 103365525 1 418 456341860 ...` view save

correct output
`604204040 604204040 604204040 ...` view save

user output
`604204040 604204040 604204040 ...` Truncated

Test 54

Verdict: ACCEPTED

input
`1000 4869 1 98 54871649 1 209 884297355 1 419 142420586 1 517 947321320 ...` view save

correct output
`563349106 845725704 796515650 ...` view save

user output
`563349106 845725704 796515650 ...` Truncated

Test 55

Verdict: ACCEPTED

input
`1000 1887 1 201 609895505 1 614 994564074 2 92 165705474 2 711 453568020 ...` view save

correct output
`453568020 559219929 559219929 ...` view save

user output
`453568020 559219929 559219929 ...` Truncated

Test 56

Verdict: ACCEPTED

input
`1000 4572 1 46 405238648 1 162 702406672 1 511 821029191 1 534 389746325 ...` view save

correct output
`798643164 798643164 798643164 ...` view save

user output
`798643164 798643164 798643164 ...` Truncated

Test 57

Verdict: ACCEPTED

input
`1000 1304 1 270 132981930 1 275 840378812 1 608 292432241 2 213 71100983 ...` view save

correct output
`221855990 272712489 411330140 ...` view save

user output
`221855990 272712489 411330140 ...` Truncated

Test 58

Verdict: ACCEPTED

input
`1000 4494 1 2 512116733 1 33 536320623 1 133 974053720 1 148 283425443 ...` view save

correct output
`652786316 858166875 858166875 ...` view save

user output
`652786316 858166875 858166875 ...` Truncated

Test 59

Verdict: ACCEPTED

input
`1000 1040 1 757 59516440 1 965 648284414 2 629 401122994 2 710 908626707 ...` view save

correct output
`22302054 22302054 22302054 223...` view save

user output
`22302054 22302054 22302054 223...` Truncated

Test 60

Verdict: ACCEPTED

input
`100000 154882 1 33511 978867794 1 62596 904646466 1 95787 49335302 2 5482 670103920 ...` view save

correct output
`443566431 443566431 233851994 ...` view save

user output
`443566431 443566431 233851994 ...` Truncated

Test 61

Verdict: ACCEPTED

input
`100000 141702 1 2516 205209909 1 57052 401636362 2 40643 139232145 2 61512 543549089 ...` view save

correct output
`139232145 205209909 205209909 ...` view save

user output
`139232145 205209909 205209909 ...` Truncated

Test 62

Verdict: ACCEPTED

input
`100000 143600 1 10252 585278633 1 27842 719546578 1 32959 489910952 1 99072 899597141 ...` view save

correct output
`499599525 499599525 499599525 ...` view save

user output
`499599525 499599525 499599525 ...` Truncated

Test 63

Verdict: ACCEPTED

input
`100000 155080 1 18730 347172856 1 62992 566295906 1 88597 621768522 2 45171 787774115 ...` view save

correct output
`564607240 367457395 227107693 ...` view save

user output
`564607240 367457395 227107693 ...` Truncated

Test 64

Verdict: ACCEPTED

input
`100000 196705 1 17467 687033132 1 24019 674209470 1 37432 745030271 1 43793 812959110 ...` view save

correct output
`696430342 515151655 701369436 ...` view save

user output
`696430342 515151655 701369436 ...` Truncated

Test 65

Verdict: ACCEPTED

input
`100000 122199 1 55264 348027668 1 97680 952735621 2 24158 324882355 2 58809 663110970 ...` view save

correct output
`249264997 155608338 397132612 ...` view save

user output
`249264997 155608338 397132612 ...` Truncated

Test 66

Verdict: ACCEPTED

input
`100000 189288 1 13135 578257724 1 26546 844229453 1 98245 997403805 2 8642 862417615 ...` view save

correct output
`626438651 487556033 633684516 ...` view save

user output
`626438651 487556033 633684516 ...` Truncated

Test 67

Verdict: ACCEPTED

input
`100000 107630 1 56075 414317534 1 95761 53615582 2 16544 826029134 2 58165 246076722 ...` view save

correct output
`53615582 53615582 53615582 536...` view save

user output
`53615582 53615582 53615582 536...` Truncated

Test 68

Verdict: ACCEPTED

input
`100000 187345 1 55230 772133163 1 72992 175103260 2 4680 820511816 2 60050 304027047 ...` view save

correct output
`631015331 546315776 528478244 ...` view save

user output
`631015331 546315776 528478244 ...` Truncated

Test 69

Verdict: ACCEPTED

input
`100000 101036 1 31139 432550553 1 32626 97199921 2 59835 174305501 2 71346 929083000 ...` view save

correct output
`2032871 2032871 2032871 203287...` view save

user output
`2032871 2032871 2032871 203287...` Truncated

Aalto Competitive Programming 2024 - wk6 - Mon

Wide delivery

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 (laluj)