fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <functional>
  5. #include <map>
  6. #include <set>
  7. using namespace std;
  8.  
  9. #define int long long
  10. #define all(c) c.begin(), c.end()
  11.  
  12. const int INF = 1LL << 60;
  13.  
  14. typedef vector<int> vi;
  15. typedef vector<vector<int>> vvi;
  16. typedef map<pair<int, int>, int> mpiii;
  17.  
  18. // Binary search helper: returns the largest index in [lo, hi] for which f(index) is true.
  19. int last_true(int lo, int hi, function<bool(int)> f) {
  20. lo--;
  21. while (lo < hi) {
  22. int mid = lo + (hi - lo + 1) / 2;
  23. if (f(mid)) lo = mid;
  24. else hi = mid - 1;
  25. }
  26. return lo;
  27. }
  28.  
  29. vvi graph;
  30. mpiii wormhole; // maps an edge (u,v) to its wormhole width
  31. vi component; // component assignment for each node
  32.  
  33. // Depth-first search that marks reachable nodes using only wormholes with width >= threshold.
  34. void dfs(int node, int threshold, int comp) {
  35. if(component[node] != -1) return;
  36. component[node] = comp;
  37. for (int adj : graph[node]) {
  38. if (wormhole[{node, adj}] >= threshold)
  39. dfs(adj, threshold, comp);
  40. }
  41. }
  42.  
  43. void solve() {
  44. int n, m;
  45. cin >> n >> m;
  46. vi p(n + 1);
  47. for (int i = 1; i <= n; i++) {
  48. cin >> p[i];
  49. }
  50.  
  51. // Prepare graph and wormhole map.
  52. graph.assign(n + 1, vi());
  53. wormhole.clear();
  54. vi widths;
  55. widths.reserve(m);
  56.  
  57. for (int i = 0; i < m; i++) {
  58. int a, b, w;
  59. cin >> a >> b >> w;
  60. graph[a].push_back(b);
  61. graph[b].push_back(a);
  62. wormhole[{a, b}] = w;
  63. wormhole[{b, a}] = w;
  64. widths.push_back(w);
  65. }
  66.  
  67. // If the cows are already sorted, no wormholes are needed.
  68. bool sorted = true;
  69. for (int i = 1; i <= n; i++) {
  70. if (i != p[i]) {
  71. sorted = false;
  72. break;
  73. }
  74. }
  75. if (sorted) {
  76. cout << -1 << "\n";
  77. return;
  78. }
  79.  
  80. // Extract candidate thresholds (unique wormhole widths) from input.
  81. vi candidates = widths;
  82. sort(all(candidates));
  83. candidates.erase(unique(all(candidates)), candidates.end());
  84.  
  85. // Binary search over candidate widths.
  86. int low = 0, high = candidates.size() - 1;
  87. int ansIndex = last_true(low, high, [&](int idx) {
  88. // Reset component assignments.
  89. component.assign(n + 1, -1);
  90. int comp = 0;
  91. for (int i = 1; i <= n; i++) {
  92. if (component[i] == -1) {
  93. dfs(i, candidates[idx], comp);
  94. comp++;
  95. }
  96. }
  97. // Check if every cow and its destination are in the same component.
  98. for (int i = 1; i <= n; i++) {
  99. if (component[i] != component[p[i]])
  100. return false;
  101. }
  102. return true;
  103. });
  104.  
  105. // If no candidate works (should not happen per problem guarantee) output -1.
  106. if (ansIndex < 0)
  107. cout << -1 << "\n";
  108. else
  109. cout << candidates[ansIndex] << "\n";
  110. }
  111.  
  112. int32_t main(){
  113. ios_base::sync_with_stdio(false);
  114. cin.tie(nullptr);
  115. int t = 1;
  116. while(t--) {
  117. solve();
  118. }
  119. return 0;
  120. }
  121.  
Success #stdin #stdout 0.01s 5284KB
stdin
100 1000
81 72 7 4 3 47 51 94 53 71 78 67 65 98 63 52 69 32 95 57 37 23 8 84 17 92 31 38 1 41 55 59 73 27 25 89 54 26 33 34 77 48 96 86 49 6 60 30 50 46 43 45 35 64 10 29 11 70 18 14 36 56 88 24 20 79 85 5 15 39 40 97 61 80 22 99 44 100 90 28 16 93 19 13 87 75 9 12 74 66 2 83 62 21 82 42 91 58 68 76
61 57 785003722
35 90 120488661
39 46 273472581
93 45 751982674
27 79 184089577
19 16 554827870
75 94 330699188
44 93 417228382
87 94 125242850
11 4 594471014
7 98 397019561
7 79 463173170
26 32 988922390
35 52 303353266
66 17 623925766
38 51 693114880
84 1 7360384
6 13 254745565
55 27 593722487
83 85 319324666
44 22 130410965
58 9 166757756
32 62 130692399
62 65 250587340
29 54 174726016
63 44 575532667
60 84 400757437
85 46 596637672
25 17 950523502
1 10 868188944
28 72 420930464
99 43 270107567
91 52 184435034
22 10 639826394
6 80 919634715
33 38 549058394
17 46 521009529
93 71 586333268
54 81 60357501
50 9 508528136
53 74 731397140
26 31 22685756
37 94 310817996
51 38 929403325
96 52 424841584
19 46 674180269
17 44 25516643
94 17 963255243
28 83 268945933
46 19 196292577
37 25 902471187
65 60 618237178
47 98 55546400
34 5 237039312
77 12 900026244
73 29 617534964
17 20 270849183
37 46 96672701
27 13 963645379
65 67 160328607
39 30 370937079
78 34 448158717
14 97 881103324
99 72 980792334
1 29 499446315
42 63 816042944
48 19 513864922
84 39 204731980
31 66 96798543
88 33 22103339
99 62 104060849
46 29 302034184
16 82 814607816
55 98 161826174
26 62 977807795
95 82 938904424
89 32 169961472
12 99 195042586
10 18 242892715
83 90 165852605
80 45 789592883
53 32 917208905
46 62 684143121
94 7 653144165
63 81 49612049
71 26 302377139
74 6 195904274
51 29 956010495
74 81 316579207
5 8 508989668
3 66 958362274
83 19 560830375
34 67 178540888
37 39 500195613
11 47 394250009
10 44 753665739
22 99 498024377
20 14 539788107
61 80 739637380
59 4 848405585
81 14 307972114
99 49 549265554
91 26 934835929
46 39 2503764
99 72 445456656
62 46 315554117
4 92 688474770
52 32 781899383
32 16 727225125
65 74 133733388
73 82 268612063
49 59 282955820
15 75 386445562
6 10 654541208
91 8 787184774
4 81 434076758
1 12 196326186
20 11 599456329
46 33 636928004
14 6 250017791
17 56 90346412
5 69 920512254
20 48 542058293
98 95 352521890
68 55 642797782
98 96 702698589
99 14 780959282
21 46 331008392
29 48 711581529
59 30 937008760
71 2 778000816
52 74 793198739
13 61 327739736
57 42 690427200
79 18 827824714
63 72 389432388
61 73 392612455
52 27 580811903
17 87 177003814
62 84 401999814
33 74 300685008
51 58 175067901
15 19 883702120
73 15 233228487
57 34 237231974
35 87 134434308
37 24 491432635
21 77 199903525
65 74 328483171
54 90 5948737
97 64 350937709
19 42 696496133
32 48 608779625
82 60 543655220
90 59 265819162
41 100 777785347
72 96 478030594
15 99 921797474
63 93 172637616
39 70 980277748
68 43 787270791
32 13 752282451
84 20 608392331
1 23 927893111
71 7 854882950
37 23 589604995
23 13 367797834
19 33 492955909
71 96 79102457
17 21 219372858
45 4 38398728
46 30 793781570
41 79 720377979
40 1 2397168
59 7 736549664
38 88 352137924
19 36 197182394
62 61 722797687
47 89 310557252
58 63 929372019
22 13 734624329
92 58 229480311
98 72 715834987
88 40 123854691
33 65 666317564
3 11 141492508
51 10 424816010
2 94 315901238
72 38 50614735
5 70 524207714
96 83 201723426
50 79 76884170
18 85 27194011
92 58 307246423
17 69 364524588
27 53 69451970
43 66 629607171
65 8 427623163
29 24 395221072
75 48 507049400
34 73 810862722
13 8 5910509
87 86 301708531
52 32 896272977
31 41 85825285
11 42 315565045
8 75 333156648
13 25 435739656
63 46 706908144
65 58 853557390
18 30 970386197
77 64 400077035
63 95 808129391
14 58 328348654
63 65 102614876
1 63 232996271
18 64 164250282
39 41 838740411
51 24 424682968
30 45 82785962
2 98 341577875
54 63 247842238
35 81 89009493
18 36 792957896
54 7 494236164
94 13 638024915
88 70 571616280
40 13 160804044
90 10 877350212
48 31 180446452
56 43 731263727
97 24 354051076
86 22 289862181
17 90 107029766
20 94 826172912
50 3 230503042
79 5 227745180
31 77 605689219
27 95 172545763
63 11 115880251
86 2 793231200
29 77 236887878
76 51 137974985
30 41 652912973
30 80 792402044
60 71 589839073
12 72 145475756
12 29 762447561
83 6 122099083
28 100 500946220
73 55 648338875
21 46 963701949
50 46 993644801
14 52 576107575
59 8 657196620
99 10 92471052
47 72 98447188
43 93 412517219
3 64 317272214
36 47 896106492
47 12 385272092
48 64 730945075
68 4 171013065
34 44 148134818
3 84 750298597
36 41 73426027
33 21 916922418
7 86 821383471
34 69 105588879
25 60 629696631
14 71 138476273
58 19 37534993
54 86 358986343
37 90 736680085
52 12 234204473
33 29 129314676
10 14 156446188
66 39 555482995
54 87 189410994
98 31 370860757
59 5 627717989
42 68 348245857
27 55 677972699
40 26 378875487
96 49 793280687
62 91 597171986
14 72 347298553
43 64 801097192
96 61 823403312
95 88 756473301
13 77 954990422
18 65 280699395
65 20 205112381
36 37 861055624
30 63 536313555
62 84 128921509
18 38 6005887
29 91 723938139
4 49 780507032
21 78 17569142
62 14 514798087
52 93 924057027
29 28 853244093
39 42 962872560
18 96 737559942
7 13 713351605
28 92 393083326
60 5 411018914
31 66 246600407
87 50 767566196
39 42 795952474
70 75 401471102
9 63 231583105
84 32 169160709
42 80 445600706
10 21 894138030
6 93 138700845
90 70 301180919
53 32 902430677
6 91 748047183
85 12 255870865
60 2 367946236
74 56 354523821
64 7 2900486
24 95 312179459
77 22 553288523
63 73 434592885
95 76 428401745
24 19 156493599
72 88 909068729
72 21 193886229
7 13 300881787
44 75 287972671
49 32 210316365
60 63 369048338
87 6 60240058
60 20 75088088
85 16 430481484
97 29 685335813
57 73 163962109
95 27 137869056
69 27 878989451
89 65 584541459
69 95 596172084
25 96 277368191
23 84 771828573
40 82 679380155
73 45 667849138
53 58 307164097
31 79 506995394
54 24 466392429
17 14 472644719
85 4 241818713
97 85 503845055
96 95 513235807
33 46 11079253
39 8 276503121
5 9 484118198
35 12 143623043
21 36 355633303
26 53 936870565
71 39 401391279
15 50 593156253
97 67 810826048
57 22 831240943
53 93 815115823
71 19 408247679
80 55 791366758
34 30 548927202
76 69 592751391
84 91 691788905
93 12 417394245
15 85 489759832
66 27 712308971
54 32 47669879
84 17 55879303
91 27 154394468
16 50 933617374
89 56 801197132
33 26 194638534
18 24 28287855
77 39 358138310
5 91 998809732
36 39 785033439
11 64 690703379
87 61 779695818
88 28 130090992
67 29 438308944
96 5 308479896
35 66 467747022
44 22 268973713
46 29 339629852
64 90 573936509
57 1 529979876
40 87 955958890
34 64 619513183
99 37 718089506
93 77 334607159
54 9 415323948
41 71 156006277
54 10 96540839
100 4 885236760
48 68 209992621
12 47 498270153
79 1 719128105
64 42 557835436
89 33 767580854
66 20 929753930
88 86 297811175
44 50 289077351
5 67 208449275
26 3 131784547
71 82 422414264
26 84 884055512
57 60 990871582
33 78 970712010
93 15 990866237
14 44 519916708
78 31 674513270
22 25 217709461
71 36 53315722
83 6 343960888
8 38 562379294
72 65 505794684
13 68 723940773
67 99 651819489
55 37 782471029
52 41 202979223
41 19 175068338
60 21 693634312
49 25 600038728
52 45 19633835
40 67 181028981
92 97 928053701
73 26 352023565
60 37 213826820
11 27 131836028
87 4 352021485
21 74 798296615
41 96 846864253
42 39 808501892
49 6 407523655
78 79 803861170
91 2 465935399
79 54 92830912
65 76 437769034
23 100 336485564
8 72 210959761
10 47 863044812
35 55 994544707
52 89 931279048
41 32 779711920
15 34 70645164
55 17 561089144
73 31 949005004
44 94 470857751
74 95 631013003
28 63 718796306
9 17 450883029
33 84 504785643
85 46 482118499
21 14 977293764
60 11 754395986
6 21 435700982
44 31 893340638
66 54 586172260
47 56 554995751
60 47 982156261
46 16 936124993
49 63 214386335
38 51 63656541
82 28 386919864
18 48 736531658
87 21 947026612
75 76 392049338
82 23 421902601
61 8 636647322
30 16 572282351
74 49 637145904
78 59 719749902
48 15 600445984
52 73 749765375
100 13 778701225
46 82 570298756
41 67 140113378
53 84 862925846
9 22 21805013
72 20 112270620
24 56 469287581
78 51 817702662
55 88 199543436
7 72 522200227
80 55 102862798
38 7 219623025
46 15 443584652
25 40 937447230
56 97 918828281
12 5 314451258
80 17 436966351
24 63 555965581
63 27 295939164
54 99 590257426
4 43 409049286
39 77 975305644
19 41 879279939
37 63 856269872
3 80 317441964
1 19 706888639
26 7 874724124
7 31 497399473
93 83 461525943
56 9 725662298
14 55 11143778
2 13 303629046
26 46 776424004
16 81 350949850
22 37 102374336
21 79 355734258
18 42 694870336
43 19 333698475
85 43 171906891
51 17 512467881
20 85 833626918
88 51 997079826
75 52 590957060
36 1 962484778
65 48 749618374
65 38 900815713
82 40 990340244
37 99 236630896
46 66 96626669
2 72 124109285
93 38 127046245
13 10 138307620
1 41 660372668
97 20 420588512
98 22 112784916
36 93 214659653
85 58 586273852
74 5 468207956
62 60 580788285
56 16 472792181
16 63 806856542
74 29 995392533
94 53 637074671
9 38 820787123
84 54 806872579
93 51 851333748
15 88 810067080
62 81 679981914
84 39 66007734
94 14 472550770
74 80 345579063
47 70 510995753
61 51 406441856
18 36 529065129
1 8 20431117
32 49 420030613
72 11 424106175
68 20 831914916
12 81 696602527
31 73 801415180
28 29 587925733
81 16 563195560
60 78 847857844
31 26 957040449
78 56 782317309
6 71 413344046
78 35 665466791
17 21 767818231
14 1 195230060
45 86 992837773
96 87 823413225
17 15 189854214
3 4 84101984
62 47 576666440
64 40 485557549
89 1 859376334
87 81 438492620
72 33 134893063
41 85 750550806
67 36 662280814
24 70 484217995
83 78 831495849
52 36 144436270
90 61 916382705
70 83 931792646
64 53 785795662
100 13 890664542
98 34 487534609
29 88 576191673
43 59 145347473
97 11 474763723
88 47 447150119
76 32 595540064
80 63 906771171
5 61 755354212
58 97 448158455
55 34 943925496
19 96 590406236
1 16 773569867
50 57 926860936
89 20 412556525
78 17 482652562
92 78 488746385
100 57 35743846
11 19 27124508
98 62 657864678
46 5 109183428
23 3 497109561
76 94 308968814
38 12 8880927
64 48 538620708
35 67 469876697
14 76 822736432
96 24 843857179
90 14 488682057
83 45 148036840
21 38 461576215
89 30 453127518
12 20 47804666
30 60 142820034
63 61 927904397
3 96 919240276
40 35 407149290
100 54 791770944
30 8 540254090
90 61 680959203
6 51 527055095
96 19 29387524
5 2 376194783
41 60 851775219
89 84 971688748
85 91 871855599
58 26 406349388
82 42 533688458
48 32 742508087
19 92 660630513
54 100 913632587
39 10 866284014
91 90 293580815
76 97 933611017
30 37 5716016
76 44 668902241
35 97 967977820
11 89 127556815
70 24 87994134
22 91 2829452
46 19 71268031
18 92 527789429
55 23 892581306
77 39 514447403
6 83 223278336
38 76 618545167
9 96 750235506
93 34 83695853
4 15 73321995
83 71 867279537
12 25 4425727
73 5 314344780
88 48 466897141
5 45 746814524
56 47 5905483
40 34 116182774
43 76 985287116
6 98 307262547
4 77 256910699
95 52 725357645
78 99 264252305
20 5 716443616
86 36 100773314
28 76 352720579
13 5 264161821
77 3 363351123
75 49 658373843
85 49 307427891
34 57 218006976
8 40 933995695
34 36 455955776
49 16 791597284
46 9 508094983
81 63 833955639
100 92 347899231
90 24 237550236
73 65 558765231
28 24 192179563
98 53 225725766
59 92 269253620
16 22 106687989
55 44 731276713
82 9 565352274
12 72 347471993
39 17 958633942
38 93 126894940
46 58 179245443
1 58 403690451
59 28 615619218
37 77 914529396
74 91 750107732
4 56 890615430
95 54 321138993
6 79 45039031
82 47 942754322
36 14 4341155
73 55 981980755
91 20 739819185
60 18 14361127
63 89 71198934
46 56 251665038
4 23 70707201
90 11 919131505
19 52 514493303
62 76 260284428
46 100 772622498
67 57 842763885
54 8 336937829
57 18 348832830
38 8 175293128
15 18 805161483
7 51 791112766
6 14 716537853
1 66 868892160
92 18 719237962
90 57 154576574
1 21 927013351
42 65 307570126
90 50 424642302
84 8 629310924
84 58 45061013
84 92 284214789
39 23 980191391
82 69 767696666
81 5 832766420
74 81 685352495
89 4 69129877
15 69 955921925
68 72 128188622
75 50 454518251
98 78 267635761
67 6 75783177
65 64 916014490
30 28 46787900
46 17 597125029
32 95 901392282
12 25 530474584
57 83 655218155
10 66 19794662
100 93 700972329
13 74 379633240
17 85 971787179
34 68 865113928
62 25 465102158
24 91 298779638
23 26 839134960
37 12 874537476
14 20 371574982
98 4 327906236
64 70 123784483
43 84 438107528
15 30 123239521
40 49 752578730
87 31 776202332
56 94 462159106
70 88 339794998
46 13 232894538
34 84 785649703
14 57 64343146
57 87 642513968
37 56 176047703
97 1 805378761
41 49 531350754
39 14 910638657
71 31 124072184
69 63 563436436
70 83 198865934
93 29 582662462
68 96 410022552
42 80 263473378
69 71 422377242
70 12 662351512
60 18 560574780
26 100 97167320
74 97 405137333
72 65 196223316
72 81 211122571
4 61 224450593
1 85 260788495
41 90 484693518
50 67 840057450
96 100 28605669
72 86 201648986
98 25 505705070
73 43 899936674
1 56 274021755
7 87 867811350
92 1 592820150
95 36 79050901
76 29 156260850
83 59 843007397
74 77 595527060
41 27 966415048
50 47 521288667
54 12 999376110
51 68 704354412
72 51 861760522
97 8 376893386
25 1 697974846
36 15 937700758
82 4 914010245
75 54 264833467
27 56 892135921
61 13 621527320
10 1 415569126
36 70 477948807
12 14 505436965
63 81 979224894
19 34 961873622
21 41 466300331
78 64 134527124
45 29 523918596
23 57 188987219
41 66 112586696
15 7 811490391
67 50 523334758
21 95 271137718
58 69 373242873
37 52 130619350
20 24 417843166
56 81 150697206
33 39 250636523
64 14 19570640
16 87 829999497
37 80 256779287
67 36 820254518
94 13 537607947
12 71 438682366
89 69 100786518
70 66 665586257
85 89 72903691
94 75 798930059
84 39 950794855
21 17 207021325
78 100 443752015
35 56 50262264
46 19 144422089
44 17 572399206
91 42 268490611
55 92 547561941
45 1 222592736
10 59 480018657
21 36 931369343
7 48 312278021
66 85 533312317
27 99 649327474
72 29 234387216
57 96 622592811
11 36 583134704
75 13 771643240
22 99 496499928
79 19 210006984
53 7 764384529
21 72 594120147
74 15 156304870
26 28 846140201
42 38 322786527
93 13 863331328
42 45 32559070
2 70 169660880
94 47 614340166
79 66 942223943
97 83 254484666
22 90 441799048
31 29 820902254
28 4 279411038
11 8 271710295
51 44 123430272
28 93 48588743
56 11 68191531
96 85 315464801
9 83 840426072
10 26 829541018
12 78 113933553
30 11 809913020
34 56 615652058
20 93 340154734
38 22 159718669
90 86 580360299
34 29 585019584
21 98 15514552
43 44 778210307
18 49 258423650
50 44 523902062
57 69 876244022
53 55 863333180
52 26 892144647
4 41 94718636
1 52 513464383
55 34 612753216
81 38 599177187
7 68 415150687
21 73 332169594
89 93 798893369
52 48 835729363
52 71 126080301
71 9 73212668
67 68 18871911
13 23 625481176
83 4 604359879
41 91 92865627
19 26 111526023
83 60 936531889
89 39 288940838
46 94 858212318
18 68 767948754
6 61 792333210
53 29 866526321
9 98 624919282
53 62 857751126
72 43 634570833
15 75 417229666
57 76 217023783
1 51 194931598
46 62 204613621
56 34 671567627
11 62 979522837
68 70 99802323
93 43 792642827
54 57 470341488
86 25 784509053
8 64 469660640
12 66 67522980
9 46 432797350
76 20 740621907
1 59 621982661
16 15 885843635
36 3 153297612
83 56 801655447
3 49 60334676
69 73 337905867
44 95 728703900
64 96 514271206
1 33 145979742
84 12 545632249
96 36 905453943
81 27 972167553
66 85 731325112
63 60 253166258
71 59 400452065
65 35 944630122
87 62 217311561
60 36 466704100
9 4 894966044
14 57 998612631
54 61 283793518
76 78 403537578
78 77 160147676
57 51 183012116
98 40 94844643
72 18 135778443
57 50 857823565
96 90 307687837
83 59 148154873
29 90 823089650
13 98 820663825
99 40 572221179
5 31 615044332
15 99 364505901
76 10 493433226
83 79 704523488
94 49 739075156
4 84 313979466
45 21 898171509
94 95 883510065
86 69 715339255
31 9 798853274
73 93 778123973
34 25 993876120
13 3 625181738
93 2 648278288
68 18 665867964
56 44 54188787
96 71 646240317
94 20 176478182
6 24 91092089
95 73 641184171
73 38 930460064
7 10 558976745
23 84 889792661
44 84 666561149
76 45 409032671
58 98 439774435
24 2 446066512
32 96 364540916
62 8 650964490
17 5 197931097
62 50 129686691
85 17 682085492
76 5 797490399
21 54 91032845
39 13 153878259
stdout
780959282