QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770143#6619. Line Graph MatchingMIS_T__WA 176ms36240kbC++232.0kb2024-11-21 20:51:342024-11-21 20:51:35

Judging History

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

  • [2024-11-21 20:51:35]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:36240kb
  • [2024-11-21 20:51:34]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
    int n,m;
    cin >> n >> m;
    i64 ans = 0;
    i64 sum = 0;
    if ( m%2 == 0 ) {
        for ( int i = 0 ; i < m ; i++ ) {
            int u,v,w;
            cin >> u >> v >> w;
            sum += w;
        }
        ans = sum;
    } else {    
        priority_queue<array<int,3>,vector<array<int,3>>,greater<>>q;
        vector g(n,vector<pair<int,int>>(0));
        for ( int i = 0 ; i < m ; i++ ) {
            int u,v,w;
            cin >> u >> v >> w;
            u--,v--;
            g[u].emplace_back(v,w);
            g[v].emplace_back(u,w);            
            sum += w;
            q.push({w,u,v});
        }
        vector<int>dfn(n);
        vector<int>low(n);
        map<pair<int,int>,pair<int,int>>mp;
        int idx = 0;
        auto tarjan = [&](auto& tarjan, int u, int f )->int{
            dfn[u] = low[u] = ++idx;
            int res = 0;
            for ( auto [v,w] : g[u] ) {
                if ( v == f ) continue;
                res++;
                if ( !dfn[v] ) {
                    int t = tarjan(tarjan,v,u);
                    low[u] = min(low[u],low[v]);
                    if ( dfn[u] < low[v] ) {
                        mp[{u,v}] = {1,t};
                        mp[{v,u}] = {1,t};
                    }
                    res += t;
                } else {
                    low[u] = min(low[u],dfn[v]);
                }
            }
            return res;
        };
        tarjan(tarjan,0,-1);
        while ( q.size() ) {
            auto [w,u,v] = q.top();
            q.pop();
            if ( mp[{u,v}].first == 1 ) {
                // cout << u << ' ' << v << ' ' << mp[{u,v}].second << '\n';
                if ( mp[{u,v}].second%2 == 0 ) {
                    ans = sum-w;
                    break;
                }
            } else {
                ans = sum-w;
                break;
            }
        }
    }
    cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3492kb

input:

5 6
1 2 1
1 3 2
1 4 3
4 3 4
4 5 5
2 5 6

output:

21

result:

ok 1 number(s): "21"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

6 5
1 2 4
2 3 1
3 4 3
4 5 2
5 6 5

output:

12

result:

ok 1 number(s): "12"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

5 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5

output:

14

result:

ok 1 number(s): "14"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

3 2
1 2 1
2 3 2

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

3 3
1 2 3
2 3 1
3 1 2

output:

5

result:

ok 1 number(s): "5"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

6 7
1 2 1
2 3 2
3 4 3
4 1 4
4 5 5
5 6 6
6 4 7

output:

27

result:

ok 1 number(s): "27"

Test #7:

score: 0
Accepted
time: 137ms
memory: 24504kb

input:

100000 99999
54273 5761 179909546
6472 21601 924153552
610 22693 767540137
37784 2454 951330587
24457 93770 781030280
36098 27 448166069
21292 43394 244510129
58047 86330 869927899
18770 83124 20504174
24036 92856 8370757
92492 21932 734860719
43776 77624 226721931
15746 70738 429430538
71204 87185 ...

output:

49946352904479

result:

ok 1 number(s): "49946352904479"

Test #8:

score: 0
Accepted
time: 140ms
memory: 24028kb

input:

100000 99999
18547 67114 422842568
19693 8496 779855087
51167 18426 915314526
44355 50210 119625069
12950 4056 197918233
61098 35840 389797594
73234 63511 535160500
47702 90861 938540623
91579 13299 509661983
40747 91690 12909789
58827 9678 282003419
35422 9560 815634437
20241 26517 840659336
93110 ...

output:

49888240257242

result:

ok 1 number(s): "49888240257242"

Test #9:

score: 0
Accepted
time: 144ms
memory: 27240kb

input:

100000 99999
25520 2623 154792857
1765 4073 799245045
99749 45838 839182660
98677 58205 524737144
76603 55928 568414838
33898 29608 922164506
88693 78722 1129358
10136 25336 739395975
69484 68712 25516570
4182 48506 515454795
76879 82061 553583242
22090 97332 926700970
89926 81197 558183206
29662 27...

output:

49857536488340

result:

ok 1 number(s): "49857536488340"

Test #10:

score: 0
Accepted
time: 140ms
memory: 34208kb

input:

100000 99999
72042 25409 725983606
49873 52758 607305688
63918 42603 224757632
7040 60725 735261849
3210 8822 867145685
41268 9352 80358220
74405 56201 74682882
42091 83435 349445732
31907 73608 324631368
21709 60815 811088936
66131 97870 754621619
50607 17635 563355884
70943 80969 555360875
34584 9...

output:

49910465246498

result:

ok 1 number(s): "49910465246498"

Test #11:

score: 0
Accepted
time: 136ms
memory: 24484kb

input:

100000 99999
10715 1068 751750885
90390 22200 868370908
4434 24771 510418099
43553 9661 532496008
33027 9192 426178660
52737 21946 668997040
54761 24810 41781655
58813 57402 176782581
36930 1300 814097421
18356 21290 10495515
24941 88423 65937531
63377 57167 347397631
72045 91846 74407074
79044 6065...

output:

50022292101614

result:

ok 1 number(s): "50022292101614"

Test #12:

score: 0
Accepted
time: 129ms
memory: 23776kb

input:

100000 99999
5344 45257 932283560
5344 41988 113638743
5344 82319 686963255
5344 83414 26663701
5344 1956 977496010
5344 95966 782365014
5344 46605 39879251
5344 96628 313951622
5344 8440 511271264
5344 49973 635326375
5344 65604 192267424
5344 47220 582095220
5344 66302 248860581
5344 73608 9553914...

output:

49915818917837

result:

ok 1 number(s): "49915818917837"

Test #13:

score: 0
Accepted
time: 148ms
memory: 23180kb

input:

100000 99999
3177 86594 412173017
12137 23850 475526600
5700 36609 945747091
42705 16895 952974711
13273 20762 127528716
36084 39413 993327177
38688 78058 261018358
64450 44338 26313078
71735 26253 140727243
34409 30797 46489921
70650 6363 519263525
85224 21135 393220205
26063 95952 740258123
23309 ...

output:

50036601113082

result:

ok 1 number(s): "50036601113082"

Test #14:

score: 0
Accepted
time: 120ms
memory: 24680kb

input:

100000 99999
22229 18543 751135535
7355 5758 89465241
25351 24408 32346633
1290 1723 708482193
2927 931 203202153
64351 62468 884908674
57054 57317 494306164
20676 19849 342091239
40940 42005 551277474
75616 77532 868037858
75616 76286 329498801
52086 54158 44517964
33660 33441 6641884
51205 53250 8...

output:

50041438241487

result:

ok 1 number(s): "50041438241487"

Test #15:

score: 0
Accepted
time: 146ms
memory: 24276kb

input:

100000 99999
12394 19008 8690121
42452 84160 98402594
66038 8702 599957491
59875 33409 967820964
48537 66162 175673729
2340 94598 64477473
71435 70892 280040195
4591 29423 438040533
96594 96303 809428076
83628 65214 722555444
52923 84089 983107819
7884 21221 978566362
68319 22916 941485643
34544 760...

output:

50030747917871

result:

ok 1 number(s): "50030747917871"

Test #16:

score: 0
Accepted
time: 149ms
memory: 23880kb

input:

100000 99999
19248 89636 592048538
87789 33340 180587215
97054 50779 296429069
76804 140 759332379
69888 97577 174834636
57616 88007 311953045
69861 26075 915540733
5651 87404 432900153
947 88542 350870091
38357 626 553637970
82250 48612 750741251
47341 61073 722847774
1946 36801 905089216
64194 577...

output:

50049230373292

result:

ok 1 number(s): "50049230373292"

Test #17:

score: 0
Accepted
time: 138ms
memory: 27844kb

input:

100000 99999
13711 11680 332787303
35706 5012 327617586
21854 88941 855853770
12391 65240 709146325
99927 7617 217470566
49623 73230 345857373
66839 28807 489450571
1696 10490 532725410
74653 85943 912435882
72806 28214 894728983
61179 1602 929957452
41015 62762 325217871
56478 28206 858783312
99762...

output:

49963658010664

result:

ok 1 number(s): "49963658010664"

Test #18:

score: 0
Accepted
time: 155ms
memory: 36240kb

input:

100000 99999
82018 91813 231145644
17460 72187 87260839
86699 26368 400610852
1654 36542 161934234
61256 8709 923500615
85905 28852 249430336
2477 37314 770689410
58222 33431 628977031
31871 14154 749797899
69983 26089 960343042
75412 60268 444667992
21146 57648 207161607
53714 93765 545567179
69362...

output:

50101850716800

result:

ok 1 number(s): "50101850716800"

Test #19:

score: 0
Accepted
time: 137ms
memory: 23576kb

input:

100000 99999
57404 6127 491298417
62367 12304 809835506
16971 73734 376362395
9046 83871 322102288
79969 66019 938472868
12266 79039 217591981
44696 85906 750602005
943 53933 950144815
32627 14682 258398683
42718 31837 811778620
49023 61736 59946130
42846 3508 614195084
74646 9394 313232749
72789 28...

output:

50007353234667

result:

ok 1 number(s): "50007353234667"

Test #20:

score: 0
Accepted
time: 145ms
memory: 23848kb

input:

100000 99999
51142 79167 448225249
51142 36261 602736753
51142 63109 68639482
51142 8207 981787380
51142 95757 735962232
51142 40048 943591187
51142 23463 528322622
51142 65417 454781301
51142 13739 987739621
51142 14376 799440656
51142 74198 440648234
51142 71812 819542848
51142 77908 137537875
511...

output:

50000048761070

result:

ok 1 number(s): "50000048761070"

Test #21:

score: 0
Accepted
time: 136ms
memory: 23196kb

input:

100000 99999
41380 4450 742905694
72767 1178 658345330
41836 91727 606060053
23188 6683 945767168
82360 68700 894838834
74976 70779 439845375
4465 2915 359272264
19120 27299 450516079
51333 80139 869168688
62603 41177 880988050
3606 5982 724478795
89908 45492 181687583
76676 62874 742769299
41046 46...

output:

50084214982614

result:

ok 1 number(s): "50084214982614"

Test #22:

score: 0
Accepted
time: 118ms
memory: 23952kb

input:

100000 99999
78401 77764 978980497
26623 18392 165370544
50100 50020 716254921
54347 58309 729940241
11346 10778 417509150
57842 56311 239110522
3668 3446 759028000
93890 97108 824865245
38907 44646 605778537
82733 82117 336069103
16226 13439 919254395
82435 82284 283702213
23232 11783 495903259
504...

output:

49971184858598

result:

ok 1 number(s): "49971184858598"

Test #23:

score: 0
Accepted
time: 170ms
memory: 24232kb

input:

100000 99999
15815 76332 967462297
26933 94251 679209512
20871 27158 336904749
47355 97819 72356433
95905 38737 423362940
22176 13699 707134600
16922 9999 131733511
91120 72194 91072031
61820 49229 496595660
21311 14373 729478328
50356 55639 62933083
62343 42000 782237152
68606 28703 111315338
24177...

output:

50038519504429

result:

ok 1 number(s): "50038519504429"

Test #24:

score: 0
Accepted
time: 165ms
memory: 24024kb

input:

100000 99999
97965 91919 542712865
85241 71148 982682514
18156 67939 452165740
81333 32746 595159778
87449 93229 159482979
98093 12256 584400929
54649 34487 494469915
57135 28720 880223084
1053 43932 852919465
74569 50441 433547801
93151 59706 996551864
74346 99709 90123498
57081 68216 885999826
533...

output:

50184925916975

result:

ok 1 number(s): "50184925916975"

Test #25:

score: 0
Accepted
time: 162ms
memory: 28408kb

input:

100000 99999
23437 95597 558083890
12083 22520 813731033
97600 74210 506952735
67237 22949 966217370
263 49706 885056060
55025 19600 837961872
27019 84910 651776260
80881 64607 68245864
31178 47346 746239124
95305 21204 954570764
97673 78340 81870718
80059 51135 424585325
96795 82404 525622153
70359...

output:

49912656271180

result:

ok 1 number(s): "49912656271180"

Test #26:

score: 0
Accepted
time: 176ms
memory: 33680kb

input:

100000 99999
79924 47648 682687236
6694 56624 583723978
35678 58604 438221076
49763 54383 975909487
59636 22518 206154719
17988 51797 688003591
21135 30889 119456905
13623 71530 179723686
90959 10978 986327056
85208 90569 721336183
88361 54734 797804982
81901 67338 411158086
97359 69174 978474784
89...

output:

50028799513444

result:

ok 1 number(s): "50028799513444"

Test #27:

score: 0
Accepted
time: 144ms
memory: 24516kb

input:

100000 99999
52051 49476 539828113
76561 22323 389415448
25402 21750 865902060
54427 68343 780762333
20363 76531 687885617
78434 48520 851019123
96225 91526 217252462
32730 93678 120206316
88877 50277 961753271
99680 11697 683078941
92379 5827 246522121
58875 98126 629886127
73664 35851 314441151
85...

output:

49924740505987

result:

ok 1 number(s): "49924740505987"

Test #28:

score: 0
Accepted
time: 129ms
memory: 23812kb

input:

100000 99999
15604 63918 622468876
15604 6251 319575978
15604 39517 864434912
15604 47078 124456945
15604 34143 899055662
15604 21298 614148372
15604 3456 251071269
15604 87759 455238974
15604 6598 672383353
15604 14038 261642271
15604 27430 942242154
15604 92005 5436329
15604 25560 130323620
15604 ...

output:

49932561573961

result:

ok 1 number(s): "49932561573961"

Test #29:

score: 0
Accepted
time: 165ms
memory: 23304kb

input:

100000 99999
51976 34949 57381634
70746 33007 450216850
35722 55266 223237115
1569 43668 201790793
72294 19509 132175490
77485 30103 80620475
17402 94257 453980362
79135 33225 987121048
41400 10203 45387586
12570 76222 894494666
40814 16097 831021040
30566 7422 205309216
4946 85722 464537900
2789 81...

output:

50015124084002

result:

ok 1 number(s): "50015124084002"

Test #30:

score: 0
Accepted
time: 141ms
memory: 26096kb

input:

100000 99999
60328 60992 394799139
35783 47077 821520469
17666 13020 76183008
27484 32051 701398163
35783 36598 303932246
18887 17188 240082019
35783 44164 619494948
59963 56466 501063295
35783 48855 380664322
32571 32927 99237272
35783 40502 728637635
35783 47620 821741012
82440 69969 525666832
211...

output:

49876639868319

result:

ok 1 number(s): "49876639868319"

Test #31:

score: 0
Accepted
time: 132ms
memory: 34668kb

input:

100000 100001
68327 31551 375564759
26193 81015 696540160
26535 75516 805635553
43459 30803 343382462
13089 23860 24975980
87640 3875 382132425
30560 81968 611719280
35043 639 896409603
30463 44082 376121726
87269 8228 599645
46129 40846 814496644
17888 67339 413013142
98976 72014 914551403
33241 39...

output:

50026081288156

result:

ok 1 number(s): "50026081288156"

Test #32:

score: 0
Accepted
time: 137ms
memory: 23456kb

input:

100000 100011
24301 64642 186822768
60826 33854 870591313
74099 72754 492511165
4261 50512 561641029
86355 55990 654974484
83149 31377 828864964
57337 43483 961257670
28050 97620 264867971
69111 7585 346877143
46018 28413 570038620
96694 63204 852982142
25713 40078 415963406
33734 65637 448195125
58...

output:

50143210038185

result:

ok 1 number(s): "50143210038185"

Test #33:

score: 0
Accepted
time: 115ms
memory: 21584kb

input:

100000 100101
55155 83883 168741671
34292 4194 732311804
68812 17957 393932542
96702 16516 687050611
26467 95664 863249457
82623 70491 184435964
77795 87455 701279641
12344 97767 552765810
7449 94827 273427280
23902 62472 853537734
82254 44033 908986382
15367 57686 104683053
94714 93259 71945485
794...

output:

50150783432523

result:

ok 1 number(s): "50150783432523"

Test #34:

score: 0
Accepted
time: 132ms
memory: 23316kb

input:

100000 101001
30092 86875 518325039
22424 61316 566927513
40897 59213 378342301
22605 47580 792158354
14398 74044 395776728
41915 63375 891754796
56522 52872 644795347
98632 3656 901759988
12060 26855 882149019
89631 20449 979316610
36319 68286 154868999
49169 94918 869911673
44394 10035 717413782
8...

output:

50418703155551

result:

ok 1 number(s): "50418703155551"

Test #35:

score: 0
Accepted
time: 122ms
memory: 22400kb

input:

100000 110001
92378 52731 416089637
27252 34439 724359284
48050 75022 936621026
34292 70974 518478851
5101 72998 218985902
17566 39206 988982202
93819 27091 438271932
79157 91840 504513498
87455 84368 804948618
93399 1084 932663474
91404 18796 910317611
84061 3963 235551592
84061 42370 708645707
293...

output:

54855020521660

result:

ok 1 number(s): "54855020521660"

Test #36:

score: 0
Accepted
time: 129ms
memory: 21952kb

input:

100000 110001
63272 47591 560844234
72400 1680 796916791
72400 97413 145968416
72400 39420 776412026
72400 45775 155046437
72400 15157 14729338
72400 85822 135845243
72400 93955 944417318
72400 45770 114993550
72400 33371 724043473
54393 5495 624187503
72400 75559 383714021
72400 37459 177937469
724...

output:

54862347565280

result:

ok 1 number(s): "54862347565280"

Test #37:

score: 0
Accepted
time: 78ms
memory: 18296kb

input:

100000 110001
10104 70664 88795653
47152 93402 22401222
43986 31680 706609108
20236 81025 92356676
42883 3625 916980440
32719 16001 372738575
68420 67686 730108449
22091 60730 515960579
84520 38364 344942541
17914 8166 682034449
52818 71413 884814285
20835 9321 740078966
43202 42747 53083614
45937 7...

output:

55054922977743

result:

ok 1 number(s): "55054922977743"

Test #38:

score: -100
Wrong Answer
time: 121ms
memory: 27416kb

input:

100000 100001
62306 59768 793757047
18142 57712 684053747
39998 92937 273820236
86396 34675 990222584
13868 96891 680154032
88694 61339 115917347
76401 41430 942573652
58542 32015 962807891
34589 20563 79372386
68582 78491 958417051
64170 2184 185878828
58092 31989 28593190
39732 24165 413772884
968...

output:

50125617240927

result:

wrong answer 1st numbers differ - expected: '50125322881599', found: '50125617240927'