QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#528810	#6758. 贸易	Qwerty1232^#	25	1436ms	4208kb	C++23	1.7kb	2024-08-23 22:28:43	2024-08-23 22:28:44

Judging History

你现在查看的是最新测评结果

[2024-08-23 22:28:44]
评测

测评结果：25
用时：1436ms
内存：4208kb

查看

[2024-08-23 22:28:43]
提交

answer

#include <bits/stdc++.h>

constexpr int mod = 998'244'353;
int add(int a, int b) {
    return a + b - mod * (a + b >= mod);
}
int mul(int a, int b) {
    return a * 1ULL * b % mod;
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int lg, m;
    std::cin >> lg >> m;
    int n = (1 << lg) - 1;
    std::vector<int> input(n - 1);
    for (int i = 0; i < n - 1; i++) {
        std::cin >> input[i];
    }
    std::vector<std::array<int, 3>> edg(m);
    for (auto& [u, v, w] : edg) {
        std::cin >> u >> v >> w;
        u--;
        v--;
    }

    std::vector<std::vector<std::pair<int, int>>> gr(n);
    for (int i = 1; i < n; i++) {
        gr[i].push_back({(i - 1) / 2, input[i - 1]});
    }
    for (auto [u, v, w] : edg) {
        gr[u].push_back({v, w});
    }

    int64_t ans = 0;
    std::vector<int64_t> dist(n);
    std::priority_queue<std::pair<int64_t, int>> heap;
    for (int i = 0; i < n; i++) {
        dist.assign(n, 1e18);
        dist[i] = 0, heap.push({0, i});
        while (heap.size()) {
            auto [d, v] = heap.top();
            heap.pop();
            d = -d;
            if (d == dist[v]) {
                for (auto [t, w] : gr[v]) {
                    if (dist[t] > d + w) {
                        dist[t] = d + w;
                        heap.push({-d - w, t});
                    }
                }
            }
        }

        int64_t ans_dlt = 0;
        for (int i = 0; i < n; i++) {
            ans_dlt += dist[i] * (dist[i] < int64_t(1e17));
            ans_dlt %= mod;
        }
        ans = (ans + ans_dlt) % mod;
    }

    std::cout << ans << "\n";

    return 0;
}

源文件, 语言: C++23

详细

Pretests

Final Tests

Test #1:

score: 5

Accepted

time: 3ms

memory: 3588kb

input:

8 200
514288401 9465107 261138494 36950916 778280149 623875874 13996134 595599538 890327813 958183330 515822328 155869551 959821159 634344485 173597565 350318575 191386048 622811198 839149762 16621220 557307463 144311203 264300211 992515513 277119988 602369433 746543323 225175710 987562782 204124558...

output:

697049410

result:

ok 1 number(s): "697049410"

Test #2:

score: 5

Accepted

time: 5ms

memory: 3816kb

input:

8 256
4556194 4891904 6780248 566137 4657301 4130549 3720079 6996786 8381898 7882559 3949573 2024861 3981763 7294856 4005685 5917128 1261488 8612618 4181215 2305135 9969340 7183867 8709972 8612230 1854164 6017851 8999327 1094604 8688933 8800341 2900585 2818436 9516784 7822610 1826489 6896383 9787623...

output:

30169050

result:

ok 1 number(s): "30169050"

Test #3:

score: 5

Accepted

time: 17ms

memory: 3560kb

input:

9 512
67529605 25818356 25867821 76428972 89560391 25483429 91191396 7807298 13422297 86663650 35163598 91635833 9540256 24825591 82607260 43906291 6200839 68073920 96904379 11945053 77795581 58354575 16583648 94124928 28443126 14266018 90534668 3638436 2845104 90223277 26101886 46458246 27277716 61...

output:

938239089

result:

ok 1 number(s): "938239089"

Test #4:

score: 5

Accepted

time: 17ms

memory: 3668kb

input:

9 512
75936829 87205090 81309985 61143625 64262968 18938520 74285118 48410072 47870690 6726792 87734672 43153650 54732326 31022846 51760206 54687907 25253122 72743315 60902757 99317027 43587656 52040170 64595684 99065511 67353069 52555729 46989703 92234225 58603280 18351710 95556865 4812552 44704137...

output:

482093226

result:

ok 1 number(s): "482093226"

Test #5:

score: 0

Time Limit Exceeded

input:

12 4000
78905602 25725648 96041176 78973350 53113543 70799435 3608093 68468474 51628778 1239062 65803606 34480276 69078148 96715840 36592980 8077032 13423873 9203745 2730658 37623534 56016540 98059537 58884581 11250500 64475232 10300254 97306131 51517787 59409088 26946678 70581737 5674099 79344055 5...

output:

result:

Test #6:

score: 0

Time Limit Exceeded

input:

12 4090
16854683 70169523 11034035 50214693 57843002 36114739 65763820 19262475 84427347 80192147 20255699 21304899 93151337 18999745 31626004 20508996 78287082 45662038 60980849 98003816 10313882 68301373 84804709 83794086 1080567 29295600 93206302 14699982 57444783 24098474 85417559 21310753 20031...

output:

result:

Test #7:

score: 5

Accepted

time: 1436ms

memory: 4208kb

input:

12 4096
119866447 108906130 143703791 174691610 152866423 195532480 175376132 116719458 102795631 198789352 139210833 94257745 116853854 163468418 155314591 121595180 118314250 197221196 61011574 150499497 171343497 163727423 174665983 52746101 78918171 155692433 159685417 198499561 56850603 1105953...

output:

149758274

result:

ok 1 number(s): "149758274"

Test #8:

score: 0

Time Limit Exceeded

input:

12 4096
88426110 80306205 94055587 93508574 84136725 57114614 60436316 50657173 81963848 67456551 58376743 97561808 90232962 56047091 96848653 73647765 68107848 55282056 98422285 72068730 87723229 80010877 79729950 65180890 76886281 69691646 65592059 89862610 94294947 97535757 51836334 67511370 6731...

output:

662919466

result:

Test #9:

score: 0

Time Limit Exceeded

input:

16 10
480356146 67540812 303733995 387723038 319676014 330936243 167409260 15613833 22623520 197388252 4783908 460764199 398216545 28095439 190570974 328642160 236457656 183083519 321109101 344665887 104582444 332898255 254523243 184105026 449547043 144454482 474663793 405805520 496021780 250396581 ...

output:

result:

Test #10:

score: 0

Time Limit Exceeded

input:

16 50
195231596 174080479 325651878 455040449 408109788 231855400 320338849 134078740 257522662 134450003 200803947 185559631 497548691 151525652 224692862 212480019 333614278 155191069 470036371 346029486 432782500 199078845 322548772 206243596 97039573 165422942 355595098 223612421 328668808 16280...

output:

result:

Test #11:

score: 0

Time Limit Exceeded

input:

16 100
104553355 96345061 241689712 370280353 127898303 461842132 444816476 234590349 266300552 348666048 261727092 495978210 332775081 58759840 451502562 478044972 240023600 234072680 249865373 201246966 275001135 95642553 65907228 88770842 464620434 116914352 72450977 411823318 290818649 50552328 ...

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

16 62913
92882372 177154170 6085859 43093644 20845259 31697709 24044361 20882222 47622131 70569153 152468333 89238284 34476330 50725533 151297125 178784923 82274286 14504285 147910957 41208044 23913580 4575160 51748703 167836229 21106671 25425519 95437066 31328900 58027123 34673543 9807541 143058972...

output:

result:

Test #13:

score: 0

Time Limit Exceeded

input:

16 65536
53995445 29899605 76424674 72420553 489026 11453478 68863738 74014358 2682747 32393876 78432745 19380545 56707168 52717353 98552665 97012875 53840068 58802459 86759503 78325856 23318136 61264110 93648786 12859730 46340034 97548060 59604 84746613 39795148 7391155 13782317 14663960 41028430 5...

output:

result:

Test #14:

score: 0

Time Limit Exceeded

input:

16 65536
86226075 69198045 6872108 90870883 61694418 44561455 46958094 63565934 53630338 28480329 49450220 52178648 22021335 29120014 19797231 71351820 10711458 86410514 25818057 71075343 11440333 79407527 23403162 35950967 69567585 26641781 78833924 21821540 95368612 53506194 63375563 71763359 8820...

output:

result:

Test #15:

score: 0

Time Limit Exceeded

input:

16 65536
344706353 320076368 752823953 719930138 239086134 596104597 496374124 189464493 895146064 507087303 446324755 772365749 600093526 591789273 870200890 595512667 298626314 71890504 38814520 236154258 841933209 703543732 761643905 850460672 380790892 841212140 232390664 636452641 149782672 927...

output:

result:

Test #16:

score: 0

Time Limit Exceeded

input:

18 262142
81212700 27191754 81786307 39443454 79130315 42498831 9493899 89971556 47420390 31536208 42249355 90509267 65811648 43799694 28780353 46406182 91560212 6786363 89885381 83341631 27483846 59078965 20329505 46904759 26408523 90691848 15142418 46201139 61548601 93169964 13138382 95083445 6488...

output:

result:

Test #17:

score: 0

Time Limit Exceeded

input:

18 249174
187446267 59706907 67932365 95805074 139701183 100058707 161150879 231409695 185263396 190849660 248612716 105472052 202878058 84214829 167841207 104826733 159421778 90543864 173256512 54438987 89270821 89499371 82324023 147256551 85090361 149558656 93980774 187178696 243750172 253032646 1...

output:

result:

Test #18:

score: 0

Time Limit Exceeded

input:

18 262144
6017407 360314644 283093879 629119395 227897142 666189428 112415072 129201209 224088551 269042705 475393847 629146039 209899852 507913276 704045160 542047971 243320371 231118293 851824409 9883676 444191949 823420819 43598363 661394671 929289912 781925357 831830581 463314898 316569818 60342...

output:

result:

Test #19:

score: 0

Time Limit Exceeded

input:

18 262144
85371280 27393378 49105877 86548916 76018613 226577 95279211 76002587 88708609 43553953 33221239 86611436 91704921 35347892 34507103 12791291 72441806 3494363 51851136 12198735 39026448 8937394 44488455 83662494 68515940 17774855 71459749 52964944 88422950 11188052 25007847 8042912 8396273...

output:

result:

Test #20:

score: 0

Time Limit Exceeded

input:

18 262144
19296072 4502993 60716893 67457285 94130162 75982547 53238950 52361332 7491712 26937668 14111002 6501812 50781448 41037290 45562418 13567694 3927265 59288850 13536861 71999224 87997504 47175715 88030430 57113207 76765495 37394566 34311254 87862445 81853378 67688853 51939618 19260793 460840...