fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef unsigned long long ull;
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef pair<int,int> pii;
  8. typedef pair<ll,ll> pll;
  9.  
  10. #define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  11. #define test() int t;cin>>t;for(int test=1;test<=t;test++)
  12. #define pb push_back
  13. #define nl cout<<"\n"
  14. #define F first
  15. #define S second
  16. #define all(x) x.begin(),x.end()
  17.  
  18. template<class C> void min_self( C &a, C b ){ a = min(a,b); }
  19. template<class C> void max_self( C &a, C b ){ a = max(a,b); }
  20.  
  21. const ll MOD = 1000000007;
  22. ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }
  23.  
  24. const int MAXN = 1e5+5;
  25. const int LOGN = 21;
  26. const ll INF = 1e14;
  27. int dx[] = {1,0,-1,0};
  28. int dy[] = {0,1,0,-1};
  29.  
  30.  
  31. class DSU
  32. {
  33. public:
  34. vector<int>rt,sz;
  35. int components;
  36. DSU( int n )
  37. {
  38. rt.resize(n+5);
  39. sz.resize(n+5);
  40. components = n;
  41. for(int i=0;i<n;i++)
  42. {
  43. rt[i] = i;
  44. sz[i] = 1;
  45. }
  46. }
  47. int get_components()
  48. {
  49. return components;
  50. }
  51. int root( int x )
  52. {
  53. while( x != rt[x] )
  54. {
  55. rt[x] = rt[rt[x]];
  56. x = rt[x];
  57. }
  58. return x;
  59. }
  60. void connect( int x, int y )
  61. {
  62. int r1 = root(x);
  63. int r2 = root(y);
  64. if( r1 == r2 )
  65. return;
  66. if( sz[r1] < sz[r2] )
  67. swap(r1,r2);
  68. sz[r1] += sz[r2];
  69. rt[r2] = r1;
  70. components--;
  71. }
  72. };
  73.  
  74.  
  75. int main()
  76. {
  77. // #ifndef ONLINE_JUDGE
  78. // freopen("../input.txt", "r", stdin);
  79. // freopen("../output.txt", "w", stdout);
  80. // #endif
  81. // freopen("wormsort.in", "r", stdin);
  82. // freopen("wormsort.out", "w", stdout);
  83. fastio();
  84.  
  85. int n,m;
  86. cin>>n>>m;
  87. vector<int>p(n);
  88. set<int>unmatched;
  89. DSU d(2*n);
  90. for(int i=0;i<n;i++)
  91. {
  92. cin>>p[i];
  93. p[i]--;
  94. if( p[i] != i )
  95. {
  96. d.connect(i+n,p[i]);
  97. unmatched.insert(i);
  98. }
  99. }
  100.  
  101. vector<vector<int>>edges(m,vector<int>(3,0));
  102. for(int i=0;i<m;i++)
  103. {
  104. int u,v,w;
  105. cin>>u>>v>>w;
  106. u--,v--;
  107. edges.pb({w,u,v});
  108. }
  109. sort(all(edges),greater<vector<int>>());
  110.  
  111. if( unmatched.empty() )
  112. {
  113. cout<<-1,nl;
  114. return 0;
  115. }
  116.  
  117. for(int i=0;i<m;i++)
  118. {
  119. int w = edges[i][0], u = edges[i][1], v = edges[i][2];
  120.  
  121. d.connect(u,v);
  122. if( d.root(u) == d.root(u+n) )
  123. unmatched.erase(u);
  124. if( d.root(v) == d.root(v+n) )
  125. unmatched.erase(v);
  126.  
  127. for( auto x : unmatched )
  128. {
  129. if( d.root(x) == d.root(x+n) )
  130. unmatched.erase(x);
  131. }
  132.  
  133. if( unmatched.empty() )
  134. {
  135. cout<<w,nl;
  136. return 0;
  137. }
  138. }
  139.  
  140.  
  141. cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  142. return 0;
  143. }
Success #stdin #stdout 0s 4356KB
stdin
4 1
1 2 3 4
4 2 13
stdout
-1