fork download
copy 
  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
comments (?)
stdin
copy 
4 1
1 2 3 4
4 2 13
stdout
copy 
-1
https://ideone.com/p4FsWr
language:
C++14 (gcc 8.3)
created:
4 years 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!