QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114950#6560. Broken Minimum Spanning TreeyangjlAC ✓17ms7940kbC++202.5kb2023-06-24 10:55:132023-06-24 10:55:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 10:55:14]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:7940kb
  • [2023-06-24 10:55:13]
  • 提交

answer

#include<iostream>
#include<cmath>
#include<cstring>
#include<cassert>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#include<unordered_set>
#include<bitset>
#include<climits>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>
#ifdef YJL
#include<debug.h>
#else
#define debug(args...)0
#define debug_n(a,n)0
#endif
using namespace std;
typedef long long ll;
struct Dsu {
    vector<int> fa, sz;
    Dsu(int n): fa(n),sz(n,1) {
        iota(fa.begin(), fa.end(), 0);
    }
    bool unite(int x, int y) {
       x=get(x), y=get(y);
       if(x==y) return false;
       fa[x]=y;
       sz[y]+=sz[x];
       return true;
    }
    int get(int x) {
        return fa[x]==x ? x: fa[x]=get(fa[x]);
    }
    int size(int x) {
        return sz[get(x)];
    }
};
const int N = 2e5 + 10;
struct ty {
    int t,l,next;
} edge[int(2e6)+10];
int en,head[N];
void initGraph(int n) {
    fill_n(head+1,n,-1),en=0;
}
void addEdge(int x,int y,int z=0) {
    edge[en]={y,z,head[x]};
    head[x]=en++;
}
int n,m,used[N],inTree[N];

vector<int> que;
bool dfs(int u,int st,int preIdx=-1) {
    for(int i=head[u]; ~i; i=edge[i].next) {
        int v=edge[i].t;
        if(!inTree[i/2]||(i^1)==preIdx) continue;
        if(!used[i/2]) que.push_back(i/2);
        if(v==st) {
            inTree[que.back()]=0;
            cout<<que.back()+1<<" ";
            que.clear();
            return true;
        }
        if(dfs(v,st,i))
            return true;
        if(!used[i/2]) que.pop_back();
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    initGraph(n);
    vector<tuple<ll,int,int,int>> e;
    for(int i=0,u,v,w; i<m; ++i) {
        cin>>u>>v>>w;
        ll temp=1ll*w*n-(i<n-1);// 原来小的还是小,原来相同的看谁原边多
        e.emplace_back(temp,u,v,i);
        addEdge(u,v);
        addEdge(v,u);
        if(i<n-1)
            inTree[i]=1;
    }

    sort(e.begin(),e.end());
    int vary=0;
    Dsu d(n+1);
    for(auto [w,u,v,id]:e) {
        if(!d.unite(u,v)) continue;
        used[id]=1;
        if(!inTree[id]) vary++;
    }
    
    cout<<vary<<'\n';
    // 寻找方案
    for(int i=0; i<m; ++i) {
        if(used[i] && !inTree[i]) {
            inTree[i]=1;
            dfs(edge[i*2].t,edge[i*2].t);
            cout<<i+1<<"\n";
        }
    }
    return 0;
}
/*




*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5472kb

input:

4 4
1 2 10
2 3 3
3 4 1
1 4 4

output:

1
1 4

result:

ok correct!

Test #2:

score: 0
Accepted
time: 1ms
memory: 5480kb

input:

6 8
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
1 3 1
4 6 1

output:

2
2 7
5 8

result:

ok correct!

Test #3:

score: 0
Accepted
time: 1ms
memory: 5588kb

input:

2000 1999
1262 1505 968661582
323 1681 787089412
1132 129 88786681
1909 587 762050278
979 1371 230688681
1686 521 980519364
975 191 887826021
869 461 899130441
1433 259 961154249
1718 547 721696188
1254 1042 458319755
1779 267 85751052
1170 813 283230029
309 20 971682908
224 417 255325364
1084 986 7...

output:

0

result:

ok correct!

Test #4:

score: 0
Accepted
time: 2ms
memory: 5688kb

input:

1999 1998
1757 1820 444157563
1757 395 754598547
1757 1571 432619009
1757 1009 456234067
1757 824 935569725
1757 1698 476714469
1757 1420 901765343
1757 1175 225295107
1757 1512 721959801
1757 1585 955067704
1757 1739 635181418
1757 1686 891225461
1757 84 132683224
1757 1696 48915557
1757 1623 42602...

output:

0

result:

ok correct!

Test #5:

score: 0
Accepted
time: 2ms
memory: 5660kb

input:

1999 1998
1345 647 232183406
40 837 279910457
819 857 137486924
255 1378 517489941
827 1565 894953662
1556 1545 898170464
965 877 72248541
1631 298 635713424
895 197 366305735
966 1160 515776809
1870 1638 220711661
1736 220 716014108
1914 1609 759121968
1293 153 272816132
1936 1433 263859075
985 460...

output:

0

result:

ok correct!

Test #6:

score: 0
Accepted
time: 1ms
memory: 5528kb

input:

500 998
105 1 1
105 2 1
105 3 1
105 4 1
105 5 1
105 6 1
105 7 1
105 8 1
105 9 1
105 10 1
105 11 1
105 12 1
105 13 1
105 14 1
105 15 1
105 16 1
105 17 1
105 18 1
105 19 1
105 20 1
105 21 1
105 22 1
105 23 1
105 24 1
105 25 1
105 26 1
105 27 1
105 28 1
105 29 1
105 30 1
105 31 1
105 32 1
105 33 1
105 ...

output:

0

result:

ok correct!

Test #7:

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

input:

500 998
364 1 1
364 2 1
364 3 1
364 4 1
364 5 1
364 6 1
364 7 1
364 8 1
364 9 1
364 10 1
364 11 1
364 12 1
364 13 1
364 14 1
364 15 1
364 16 1
364 17 1
364 18 1
364 19 1
364 20 1
364 21 1
364 22 1
364 23 1
364 24 1
364 25 1
364 26 1
364 27 1
364 28 1
364 29 1
364 30 1
364 31 1
364 32 1
364 33 1
364 ...

output:

0

result:

ok correct!

Test #8:

score: 0
Accepted
time: 1ms
memory: 5596kb

input:

500 998
86 1 2
86 2 2
86 3 2
86 4 2
86 5 2
86 6 2
86 7 2
86 8 2
86 9 2
86 10 2
86 11 2
86 12 2
86 13 2
86 14 2
86 15 2
86 16 2
86 17 2
86 18 2
86 19 2
86 20 2
86 21 2
86 22 2
86 23 2
86 24 2
86 25 2
86 26 2
86 27 2
86 28 2
86 29 2
86 30 2
86 31 2
86 32 2
86 33 2
86 34 2
86 35 2
86 36 2
86 37 2
86 38...

output:

499
1 500
2 501
3 502
4 503
5 504
6 505
7 506
8 507
9 508
10 509
11 510
12 511
13 512
14 513
15 514
16 515
17 516
18 517
19 518
20 519
21 520
22 521
23 522
24 523
25 524
26 525
27 526
28 527
29 528
30 529
31 530
32 531
33 532
34 533
35 534
36 535
37 536
38 537
39 538
40 539
41 540
42 541
43 542
44 5...

result:

ok correct!

Test #9:

score: 0
Accepted
time: 1ms
memory: 5588kb

input:

500 998
198 227 1
227 315 1
315 426 1
426 400 1
400 61 1
61 143 1
143 487 1
487 65 1
65 415 1
415 434 1
434 327 1
327 190 1
190 411 1
411 51 1
51 91 1
91 364 1
364 185 1
185 393 1
393 89 1
89 53 1
53 66 1
66 69 1
69 13 1
13 5 1
5 45 1
45 314 1
314 291 1
291 490 1
490 92 1
92 175 1
175 458 1
458 218 ...

output:

0

result:

ok correct!

Test #10:

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

input:

500 998
360 250 1
250 71 1
71 170 1
170 492 1
492 419 1
419 145 1
145 188 1
188 433 1
433 186 1
186 161 1
161 398 1
398 19 1
19 479 1
479 401 1
401 40 1
40 176 1
176 212 1
212 353 1
353 290 1
290 43 1
43 322 1
322 447 1
447 47 1
47 468 1
468 456 1
456 343 1
343 339 1
339 52 1
52 251 1
251 130 1
130 ...

output:

0

result:

ok correct!

Test #11:

score: 0
Accepted
time: 5ms
memory: 7672kb

input:

500 998
369 45 2
45 364 2
364 300 2
300 195 2
195 291 2
291 390 2
390 122 2
122 331 2
331 408 2
408 91 2
91 298 2
298 116 2
116 301 2
301 287 2
287 338 2
338 4 2
4 79 2
79 177 2
177 387 2
387 125 2
125 477 2
477 11 2
11 284 2
284 102 2
102 305 2
305 395 2
395 112 2
112 280 2
280 294 2
294 232 2
232 ...

output:

499
10 500
182 501
483 502
428 503
484 504
250 505
172 506
116 507
180 508
82 509
275 510
178 511
148 512
13 513
380 514
54 515
393 516
382 517
53 518
72 519
225 520
493 521
279 522
490 523
216 524
386 525
18 526
122 527
358 528
136 529
230 530
48 531
344 532
315 533
104 534
150 535
151 536
205 537
...

result:

ok correct!

Test #12:

score: 0
Accepted
time: 2ms
memory: 5544kb

input:

500 998
298 314 1
467 314 1
9 314 1
345 298 1
497 298 1
315 467 1
147 345 1
154 345 1
16 345 1
226 497 1
406 147 1
204 298 1
351 406 1
432 314 1
274 406 1
340 274 1
395 226 1
173 315 1
180 274 1
207 9 1
495 204 1
213 298 1
413 207 1
450 204 1
25 147 1
161 497 1
231 180 1
175 467 1
199 231 1
454 231 ...

output:

0

result:

ok correct!

Test #13:

score: 0
Accepted
time: 2ms
memory: 5560kb

input:

500 998
42 349 1
256 42 1
202 349 1
23 42 1
252 42 1
175 42 1
67 252 1
302 67 1
337 252 1
495 252 1
14 349 1
347 202 1
494 495 1
206 347 1
1 302 1
434 349 1
475 206 1
243 206 1
135 494 1
179 495 1
226 202 1
490 226 1
481 1 1
165 243 1
114 495 1
463 256 1
282 114 1
411 202 1
25 1 1
163 67 1
388 179 1...

output:

0

result:

ok correct!

Test #14:

score: 0
Accepted
time: 3ms
memory: 5540kb

input:

500 998
493 328 2
444 493 2
356 328 2
374 328 2
135 328 2
292 444 2
323 135 2
296 328 2
407 493 2
207 374 2
118 296 2
490 135 2
357 323 2
464 292 2
279 323 2
183 493 2
81 356 2
367 407 2
235 356 2
354 292 2
479 464 2
214 118 2
406 357 2
164 279 2
230 356 2
380 164 2
399 135 2
344 81 2
190 490 2
422 ...

output:

499
1 500
2 501
3 502
4 503
5 504
6 505
7 506
8 507
9 508
10 509
11 510
12 511
13 512
14 513
15 514
16 515
17 516
18 517
19 518
20 519
21 520
22 521
23 522
24 523
25 524
26 525
27 526
28 527
29 528
30 529
31 530
32 531
33 532
34 533
35 534
36 535
37 536
38 537
39 538
40 539
41 540
42 541
43 542
44 5...

result:

ok correct!

Test #15:

score: 0
Accepted
time: 2ms
memory: 7544kb

input:

10 20
3 5 132699872
7 3 667475629
10 7 829222331
1 7 265644695
4 3 226461311
2 7 720348681
6 10 703702759
8 4 153004599
9 10 646988804
1 9 45480111
2 4 784301144
1 9 628023542
7 8 449200681
9 2 240371799
3 2 420603433
3 9 838425734
4 6 623790050
1 7 513829155
1 9 883183260
10 3 422484921

output:

5
9 10
6 14
2 15
7 17
3 20

result:

ok correct!

Test #16:

score: 0
Accepted
time: 1ms
memory: 7540kb

input:

100 200
69 52 334673965
90 52 598347660
62 52 671196898
38 90 561150605
97 69 844448459
25 90 865251171
41 38 773653441
49 97 813975775
99 41 996226580
54 69 583281785
34 38 385173507
56 97 285801905
17 38 946715780
67 17 139770128
43 97 890101081
68 90 370458274
74 17 698466900
6 67 19950896
58 56 ...

output:

50
39 103
65 104
10 107
64 108
8 109
47 112
74 115
69 116
2 120
15 121
92 125
80 126
25 127
36 131
21 132
9 134
5 135
87 136
24 137
16 138
83 145
28 148
41 150
89 152
7 153
75 156
60 157
61 160
77 163
19 166
44 168
96 170
35 171
49 174
3 176
4 177
45 180
81 181
58 182
17 183
20 184
95 185
23 186
13 ...

result:

ok correct!

Test #17:

score: 0
Accepted
time: 16ms
memory: 5676kb

input:

2000 3000
1279 1465 434468566
1062 1279 993799662
1494 1465 490141333
529 1279 207090506
119 1279 494706603
1830 1062 798435525
1307 1279 501822892
362 119 776215279
1330 1494 64095945
1823 529 302809447
1882 529 298925061
1394 529 639185117
1852 362 939130818
752 529 845078929
104 752 853251112
126...

output:

617
124 2000
1046 2001
31 2002
1975 2003
773 2008
1538 2009
95 2011
6 2014
133 2016
1992 2017
963 2018
100 2019
147 2021
161 2023
977 2025
401 2026
176 2027
627 2029
13 2030
87 2031
58 2033
567 2034
572 2037
116 2038
78 2040
16 2041
272 2043
1184 2045
1643 2046
368 2047
8 2048
15 2049
560 2050
912 2...

result:

ok correct!

Test #18:

score: 0
Accepted
time: 17ms
memory: 5700kb

input:

2000 3000
285 1808 694643588
224 285 690510187
908 1808 663193044
486 224 663712643
324 908 165916788
1403 285 948845412
1310 324 12561437
1948 285 642808470
883 1310 358793640
396 1808 869731392
1276 1310 621641177
203 1948 231802320
1547 1276 39692873
830 285 636658714
1357 1948 177401445
303 203 ...

output:

613
19 2000
1110 2001
362 2003
636 2004
16 2006
1131 2007
478 2008
50 2009
41 2010
1674 2011
629 2015
181 2016
1522 2017
950 2018
1927 2019
1325 2021
24 2022
463 2023
167 2024
17 2027
315 2028
31 2029
527 2031
912 2034
341 2035
1351 2037
1255 2039
376 2042
928 2043
854 2045
400 2048
1647 2049
90 205...

result:

ok correct!

Test #19:

score: 0
Accepted
time: 17ms
memory: 5712kb

input:

2000 3000
1966 1337 886061561
1564 1966 321739163
878 1966 383102115
15 1337 355428698
392 15 389233814
1520 1337 163779508
1349 392 323493610
1126 1349 804548395
1739 1337 508691040
956 1564 924027693
674 1126 845489957
1749 1739 290423046
1926 1966 647294733
456 1966 656155212
1746 1564 106274278
...

output:

603
1382 2000
373 2001
1090 2002
228 2005
348 2006
1238 2007
86 2008
1878 2010
106 2011
586 2012
380 2014
1424 2016
133 2017
1140 2019
162 2021
10 2022
167 2023
590 2024
1552 2025
144 2026
1923 2027
1859 2028
525 2031
196 2032
9 2033
265 2035
77 2037
80 2039
48 2041
11 2042
272 2044
1298 2046
918 20...

result:

ok correct!

Test #20:

score: 0
Accepted
time: 13ms
memory: 5724kb

input:

2000 3000
487 1828 891595258
848 1828 70120465
399 1828 222566316
2000 1828 390057442
589 487 561090448
1878 399 923567050
1547 848 289163461
724 1828 712597149
856 487 612088317
1932 848 498697630
177 1932 225589816
1541 856 745128386
1229 399 501103338
40 1828 283700123
1206 1878 364593718
519 40 ...

output:

624
1332 2000
1296 2002
563 2003
1878 2007
1383 2008
717 2010
633 2011
608 2013
43 2014
1132 2017
1264 2018
178 2019
805 2020
1681 2022
459 2023
1628 2024
1715 2025
1505 2026
1661 2027
1427 2028
501 2031
9 2032
1905 2034
266 2035
1446 2039
12 2040
577 2042
1514 2045
5 2046
1012 2047
1323 2048
6 2051...

result:

ok correct!

Test #21:

score: 0
Accepted
time: 12ms
memory: 5680kb

input:

2000 3000
28 909 901469954
874 909 630039044
1150 874 369081856
180 1150 796073964
199 874 607566492
1260 1150 672891947
233 180 524809142
390 909 531859461
122 874 275924720
457 1260 521407422
872 28 975420599
497 872 901775699
885 390 839588422
1242 199 380484388
1598 28 823494399
202 885 41696165...

output:

618
369 2000
201 2004
450 2005
1427 2006
134 2007
1765 2008
1271 2009
613 2010
409 2013
1644 2016
38 2018
12 2019
750 2020
1811 2025
368 2026
7 2027
144 2029
618 2030
56 2031
437 2033
1700 2035
502 2037
563 2038
285 2039
27 2040
116 2043
823 2044
324 2047
197 2050
256 2051
1658 2052
41 2053
1100 205...

result:

ok correct!

Test #22:

score: 0
Accepted
time: 2ms
memory: 7660kb

input:

2 3000
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1
1 2 1...

output:

0

result:

ok correct!

Test #23:

score: 0
Accepted
time: 1ms
memory: 5848kb

input:

2000 2000
273 274 976318149
1818 1819 911362963
920 921 733992701
1147 1148 968069222
1076 1077 479630568
1576 1577 723601562
860 861 477629418
747 748 636289483
219 220 254346042
610 611 561106993
1173 1174 117741584
1788 1789 433959137
437 438 566901968
723 724 578256290
984 985 201368344
954 955 ...

output:

1
1575 2000

result:

ok correct!

Test #24:

score: 0
Accepted
time: 9ms
memory: 5876kb

input:

2000 2500
1936 1937 470205868
750 751 637463850
75 76 353874306
1012 1013 575007557
679 680 452883390
268 269 382879319
1885 1886 619233286
1617 1618 985926999
365 366 731212904
703 704 136815299
1543 1544 6628104
1586 1587 963856921
1904 1905 377843376
254 255 540189789
690 691 218468543
1169 1170 ...

output:

371
413 2000
672 2002
1287 2003
986 2004
1839 2006
1677 2007
1555 2008
1201 2010
916 2011
1684 2012
1302 2013
61 2015
1813 2017
1256 2018
1177 2022
8 2023
888 2024
1206 2025
1362 2026
1430 2027
849 2028
1377 2029
124 2031
275 2032
266 2033
1735 2035
1842 2036
915 2038
508 2039
1883 2040
1435 2041
59...

result:

ok correct!

Test #25:

score: 0
Accepted
time: 14ms
memory: 7940kb

input:

2000 3000
1100 1101 966680160
584 585 619523116
196 197 969093892
1265 1266 112963336
1463 1464 437550508
1320 1321 888461822
1414 1415 755948833
897 898 48495011
365 366 564439441
869 870 108232038
1323 1324 469077928
1432 1433 609528786
1885 1886 447585062
81 82 480544752
1819 1820 385633491
1371 ...

output:

588
1034 2000
311 2001
1930 2002
719 2003
1732 2004
1906 2005
1942 2008
1387 2009
1647 2010
1893 2011
1544 2018
1626 2020
1607 2021
1733 2025
1777 2026
1600 2027
1612 2028
1760 2030
1772 2031
827 2034
269 2035
426 2037
1102 2040
668 2043
600 2044
1520 2045
1088 2046
1595 2047
72 2053
1395 2054
1714 ...

result:

ok correct!

Test #26:

score: 0
Accepted
time: 1ms
memory: 5492kb

input:

10 18
2 6 2
6 1 2
1 10 2
10 4 2
4 3 2
3 9 2
9 8 2
8 5 2
5 7 2
2 4 1
4 10 1
10 3 1
3 5 1
5 6 1
6 7 1
7 8 1
8 1 1
1 9 1

output:

9
4 10
3 11
5 12
8 13
1 14
9 15
7 16
2 17
6 18

result:

ok correct!