fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <map>
  6. #include <set>
  7. #include <queue>
  8. #include <stack>
  9. #include <deque>
  10. #include <functional>
  11. #include <bitset>
  12. #include <cmath>
  13. #include <cstdio>
  14. #include <cstdlib>
  15. #include <cstring>
  16. #include <climits>
  17. #include <cassert>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <numeric>
  21. #include <iterator>
  22. #include <iomanip>
  23.  
  24. #define int long long
  25. using namespace std;
  26. #define all(c) c.begin(), c.end()
  27. #define rall(c) c.rbegin(), c.rend()
  28. const int INF = 1LL << 60;
  29. const int NEG_INF = -1000000000000000000LL;
  30. typedef pair<int, int> pii;
  31. typedef vector<int> vi;
  32. typedef vector<bool> vb;
  33. typedef vector<vector<int>> vvi;
  34. typedef vector<vector<bool>> vvb;
  35. typedef vector<pair<int, int>> vpii;
  36. typedef vector<set<int>> vsi;
  37. typedef vector<pair<int, pair<int, int>>> vpipii;
  38. typedef set<int> si;
  39. typedef set<char> sc;
  40. typedef map<int, int> mii;
  41. typedef map<int, pair<int, int>> mipii;
  42. typedef map<pair<int, int>, int> mpiii;
  43. typedef vector<double> vd;
  44. typedef vector<pair<double, double>> vpdd;
  45. typedef multiset<int> msi;
  46. typedef queue<int> qi;
  47. #define mp make_pair
  48. #define pb push_back
  49. #define line "\n"
  50.  
  51. #define FOR(i, a, b) for (int i = a; i < b; i++)
  52. #define F0R(i, a) for (int i = 0; i < a; i++)
  53.  
  54. #define f first
  55. #define s second
  56. #define lb lower_bound
  57. #define ub upper_bound
  58.  
  59. vector<int> vector_set(vector<int> indices) {
  60.     sort(indices.begin(), indices.end());
  61.     indices.erase(unique(indices.begin(), indices.end()), indices.end());
  62.     return indices;
  63. }
  64. int first_true(int lo, int hi, function<bool(int)> f) {
  65.     hi++;
  66.     while (lo < hi) {
  67.         int mid = lo + (hi - lo) / 2;
  68.         if (f(mid)) hi = mid;
  69.         else lo = mid + 1;
  70.     }
  71.     return lo;
  72. }
  73. int last_true(int lo, int hi, function<bool(int)> f) {
  74.     lo--;
  75.     while (lo < hi) {
  76.         int mid = lo + (hi - lo + 1) / 2;
  77.         if (f(mid)) lo = mid;
  78.         else hi = mid - 1;
  79.     }
  80.     return lo;
  81. }
  82. double first_true_double(double lo, double hi, std::function<bool(double)> f, double eps = 1e-6) {
  83.     while (hi - lo > eps) {
  84.         double mid = lo + (hi - lo) / 2.0;
  85.         if (f(mid))
  86.             hi = mid;
  87.         else
  88.             lo = mid;
  89.     }
  90.     return hi;
  91. }
  92. double last_true_double(double lo, double hi, std::function<bool(double)> f, double eps = 1e-6) {
  93.     while (hi - lo > eps) {
  94.         double mid = lo + (hi - lo) / 2.0;
  95.         if (f(mid))
  96.             lo = mid;
  97.         else
  98.             hi = mid;
  99.     }
  100.     return lo;
  101. }
  102.  
  103. const int N = 1e6;
  104. vvi graph(N);
  105. mpiii location;
  106.  
  107. void dfs(int node, int width, vb &vis, vi &travel) {
  108.     if (vis[node]) return;
  109.     vis[node] = true;
  110.     travel.pb(node);
  111.     for (int adj : graph[node]) {
  112.         int current_width = location[{node, adj}];
  113.         if (current_width <= width)
  114.             dfs(adj, width, vis, travel);
  115.     }
  116. }
  117.  
  118. void solve() {
  119.     int n, m; 
  120.     cin >> n >> m;
  121.     vi p(n), w(m + 1); 
  122.     w[0] = 0;
  123.     F0R(i, n) 
  124.         cin >> p[i];
  125.     F0R(i, m) {
  126.         int x, y; 
  127.         cin >> x >> y >> w[i + 1];
  128.         x--; y--;
  129.         graph[x].pb(y);
  130.         graph[y].pb(x);
  131.         location[{x, y}] = w[i + 1];
  132.         location[{y, x}] = w[i + 1];
  133.     }
  134.     sort(all(w));
  135.     int ans = first_true(0, m, [&](int x) {
  136.         int width = w[x];
  137.         // Reinitialize the visited vector and clear component storage
  138.         vb vis(n, false);
  139.         vvi travel_complete;
  140.         // Run DFS for each component with the current threshold
  141.         F0R(i, n) {
  142.             if (!vis[i]) {
  143.                 vi travel;
  144.                 dfs(i, width, vis, travel);
  145.                 travel_complete.pb(travel);
  146.             }
  147.         }
  148.         // Build DSU-like connectivity sets
  149.         vsi dsu(n);
  150.         for (auto comp : travel_complete) {
  151.             for (int k : comp) {
  152.                 // Insert all nodes from the component into dsu[k]
  153.                 dsu[k].insert(comp.begin(), comp.end());
  154.             }
  155.         }
  156.         bool ok = false;
  157.         F0R(i, n) {
  158.             if (i != p[i]) {
  159.                 if (dsu[i].find(p[i]) != dsu[i].end()) {
  160.                     ok = true;
  161.                     break;
  162.                 }
  163.             }
  164.         }
  165.         return !ok;
  166.     });
  167.     if(ans == 0) cout << -1 << line;
  168.     else cout << w[ans] << line;
  169. }
  170.  
  171. int32_t main() {
  172.     ios_base::sync_with_stdio(false);
  173.     cin.tie(NULL);
  174.     cout.tie(NULL);
  175.     int t = 1;
  176.     while(t-- > 0) {
  177.         solve();
  178.     }
  179.     return 0;
  180. }
  181.  
Success #stdin #stdout 0.01s 26720KB
comments ()
stdin
copy 
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
stdout
copy 
-1
https://ideone.com/aoTZiX
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!