QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111395#6560. Broken Minimum Spanning Treehos_lyricAC ✓19ms3804kbC++142.9kb2023-06-06 22:54:202023-06-06 22:54:22

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-06 22:54:22]
  • 评测
  • 测评结果:AC
  • 用时:19ms
  • 内存:3804kb
  • [2023-06-06 22:54:20]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


vector<int> uf;
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


int N, M;
vector<int> A, B, W;

int main() {
  for (; ~scanf("%d%d", &N, &M); ) {
    A.resize(M);
    B.resize(M);
    W.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d", &A[i], &B[i], &W[i]);
      --A[i];
      --B[i];
    }
    
    vector<pair<int, int>> es(M);
    for (int i = 0; i < M; ++i) {
      es[i] = make_pair(W[i] << 1 | ((i < N - 1) ? 0 : 1), i);
    }
    sort(es.begin(), es.end());
    uf.assign(N, -1);
    vector<int> tar(M, 0);
    for (const auto &e : es) {
      const int i = e.second;
      if (connect(A[i], B[i])) {
        tar[i] = 1;
      }
    }
    
    vector<int> on(M, 0);
    for (int i = 0; i < N - 1; ++i) {
      on[i] = 1;
    }
    vector<pair<int, int>> ans;
    for (; ; ) {
      int im = -1;
      for (int i = 0; i < M; ++i) if (on[i] && !tar[i]) {
        im = i;
        break;
      }
      if (!~im) {
        break;
      }
      on[im] = 0;
      uf.assign(N, -1);
      for (int i = 0; i < M; ++i) if (on[i]) {
        connect(A[i], B[i]);
      }
      for (int i = 0; i < M; ++i) if (!on[i] && tar[i]) {
        if (root(A[i]) != root(B[i])) {
          on[i] = 1;
          ans.emplace_back(im, i);
          goto found;
        }
      }
      assert(false);
     found:{}
    }
    
    printf("%d\n", (int)ans.size());
    for (const auto &op : ans) {
      printf("%d %d\n", op.first + 1, op.second + 1);
    }
  }
  return 0;
}

詳細信息

Test #1:

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

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: 0ms
memory: 3644kb

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: 2ms
memory: 3748kb

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: 3704kb

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: 3792kb

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: 2ms
memory: 3716kb

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: 2ms
memory: 3700kb

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: 2ms
memory: 3676kb

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: 0ms
memory: 3656kb

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: 2ms
memory: 3700kb

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: 4ms
memory: 3712kb

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
1 826
2 743
3 651
4 800
5 992
6 845
7 867
8 789
9 911
10 500
11 926
12 572
13 513
14 882
15 720
16 941
17 554
18 526
19 568
20 964
21 593
22 748
23 828
24 744
25 579
26 942
27 909
28 707
29 681
30 633
31 947
32 592
33 990
34 904
35 742
36 723
37 899
38 621
39 898
40 709
41 552
42 769
43 580
44 5...

result:

ok correct!

Test #12:

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

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: 3696kb

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: 4ms
memory: 3676kb

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: 3736kb

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
2 15
3 10
6 14
7 17
9 20

result:

ok correct!

Test #16:

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

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
2 104
3 107
4 112
5 108
6 120
7 134
8 109
9 145
10 135
13 115
15 121
16 127
17 103
19 157
20 116
21 125
23 186
24 137
25 153
28 138
31 194
35 171
36 131
39 183
41 126
44 150
45 132
47 160
49 174
50 195
52 152
58 177
60 176
61 168
64 148
65 180
67 184
69 166
71 190
74 182
75 156
77 163
80 189
81 1...

result:

ok correct!

Test #17:

score: 0
Accepted
time: 19ms
memory: 3804kb

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
2 2014
3 2009
6 2061
7 2000
8 2001
12 2021
13 2002
14 2018
15 2040
16 2016
17 2057
19 2011
22 2034
23 2622
26 2332
27 2769
31 2017
33 2023
34 2038
35 2052
37 2082
39 2154
40 2251
41 2092
45 2043
46 2058
48 2008
49 2025
51 2019
54 2003
55 2029
57 2047
58 2027
61 2031
62 2062
63 2091
64 2125
65 25...

result:

ok correct!

Test #18:

score: 0
Accepted
time: 19ms
memory: 3800kb

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
1 2001
2 2000
3 2008
4 2017
6 2015
8 2016
10 2018
11 2003
14 2022
16 2006
17 2009
19 2004
20 2010
21 2511
24 2031
25 2079
31 2029
34 2160
35 2062
36 2056
40 2024
41 2007
42 2078
44 2021
48 2145
49 2061
50 2057
52 2143
56 2137
60 2370
61 2019
65 2185
66 2287
70 2153
75 2282
77 2042
79 2206
80 207...

result:

ok correct!

Test #19:

score: 0
Accepted
time: 19ms
memory: 3772kb

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
1 2002
3 2001
8 2006
9 2011
10 2000
11 2007
13 2049
14 2012
18 2017
20 2022
21 2021
22 2047
23 2076
24 2019
30 2238
37 2081
38 2041
41 2016
42 2005
43 2110
46 2026
47 2066
48 2122
50 2039
53 2048
54 2027
55 2042
56 2028
60 2031
61 2051
67 2450
68 2378
73 2024
75 2062
77 2078
79 2079
80 2086
84 2...

result:

ok correct!

Test #20:

score: 0
Accepted
time: 15ms
memory: 3768kb

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
1 2013
5 2018
6 2002
8 2022
9 2045
10 2003
12 2027
13 2008
17 2034
18 2051
21 2007
22 2023
29 2020
30 2032
33 2010
39 2155
40 2060
41 2039
43 2014
44 2048
45 2025
49 2047
50 2059
52 2077
53 2131
55 2149
56 2161
61 2146
66 2035
68 2081
69 2111
70 2644
72 2170
73 2062
79 2024
80 2028
81 2143
82 20...

result:

ok correct!

Test #21:

score: 0
Accepted
time: 19ms
memory: 3768kb

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
1 2009
2 2007
4 2004
5 2006
6 2008
7 2259
8 2010
10 2005
11 2018
12 2019
13 2262
15 2029
18 2035
19 2013
20 2000
22 2100
23 2016
26 2228
27 2080
28 2026
29 2040
30 2038
32 2025
33 2031
37 2079
38 2027
41 2047
46 2030
47 2051
52 2044
56 2066
60 2106
61 2059
62 2329
64 2050
65 2064
67 2057
69 2071...

result:

ok correct!

Test #22:

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

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: 3684kb

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: 13ms
memory: 3752kb

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
8 2000
9 2004
22 2015
24 2003
31 2018
32 2007
36 2010
39 2006
49 2012
50 2013
54 2017
61 2022
65 2086
67 2070
69 2002
75 2103
76 2024
88 2025
97 2064
99 2133
110 2027
124 2099
125 2026
130 2119
135 2033
147 2043
149 2083
159 2023
160 2097
166 2032
175 2042
177 2029
179 2268
183 2011
185 2035
189...

result:

ok correct!

Test #25:

score: 0
Accepted
time: 18ms
memory: 3728kb

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
1 2000
3 2001
6 2002
9 2021
11 2222
17 2009
19 2008
22 2011
24 2003
36 2026
39 2034
41 2005
45 2018
50 2027
51 2053
55 2010
59 2066
69 2020
72 2192
75 2025
79 2046
82 2202
93 2189
94 2044
95 2057
96 2043
98 2040
106 2089
108 2116
111 2073
112 2030
118 2199
120 2460
122 2028
124 2088
131 2071
134...

result:

ok correct!

Test #26:

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

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
1 10
2 14
3 17
4 11
5 12
6 13
7 18
8 16
9 15

result:

ok correct!