fork download
copy 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26. #define SZ(x) ((int)(x).size())
  27.  
  28. using namespace std;
  29.  
  30. typedef long long vlong;
  31. typedef unsigned long long uvlong;
  32. typedef pair < int, int > pii;
  33. typedef pair < vlong, vlong > pll;
  34. typedef vector<pii> vii;
  35. typedef vector<int> vi;
  36.  
  37. const vlong inf = 2147383647;
  38. /***********Template Ends Here***********/
  39.  
  40. vii adj[1000100];
  41. int ign;
  42. int vis[1000010], col[1000010], vv;
  43.  
  44. int n;
  45. bool bicolor;
  46.  
  47. ///Bicolor the graph
  48. int dfs ( int s, int p ) {
  49.     vis[s] = vv;
  50.  
  51.     FOR(i,0,SZ(adj[s])-1) {
  52.         pii temp = adj[s][i];
  53.         int t = temp.ff;
  54.         int w = temp.ss;
  55.  
  56.         if ( w >= ign ) continue;
  57.  
  58.         if ( t == p ) continue;
  59.  
  60.         if ( vis[t] != vv ) {
  61.             col[t] = 1 - col[s];
  62.             dfs ( t, s );
  63.         }
  64.         else {
  65.             if ( col[t] == col[s] ) {
  66.                 bicolor = false;
  67.             }
  68.         }
  69.     }
  70. }
  71.  
  72. ///Check if graph is bipartite
  73. bool bipartite ( int len ) {
  74.     ign = len;
  75.     vv++;
  76.  
  77.     bicolor = true;
  78.     FOR(i,1,n) {
  79.         if ( vis[i] != vv ) {
  80.             col[i] = 0; ///White
  81.             dfs ( i, -1 );
  82.             if ( bicolor == false ) return false;
  83.         }
  84.     }
  85.  
  86.     return true;
  87. }
  88.  
  89. int main () {
  90.     int kase;
  91.     scanf ( "%d", &kase );
  92.  
  93.     while ( kase-- ) {
  94.         int m;
  95.         scanf ( "%d %d", &n, &m );
  96.  
  97.         FOR(i,1,n) adj[i].clear();
  98.  
  99.         int mx = 0, mn = inf;
  100.         FOR(i,0,m-1) {
  101.             int a, b, c;
  102.             scanf ( "%d %d %d", &a, &b, &c );
  103.  
  104.             adj[a].pb ( MP(b,c) );
  105.             adj[b].pb ( MP(a,c) );
  106.  
  107.             mx = MAX(mx,c);
  108.             mn = MIN(mn,c);
  109.         }
  110.  
  111.         bool res = bipartite( mx + 1 ); ///Keep all the edges
  112.         if ( res ) {
  113.             printf ( "%d\n", 0 );
  114.             continue;
  115.         }
  116.  
  117.         int low = 1, high = mx;
  118.  
  119.         while ( low <= high ) {
  120.             int mid = ( low + high ) / 2;
  121.  
  122.             res = bipartite ( mid );
  123.  
  124.             if ( res ) {
  125.                 low = mid + 1;
  126.             }
  127.             else high = mid - 1;
  128.         }
  129.  
  130.         if ( low - 1 == mn ) low = 0; ///Need to remove all edges. So answer is -1
  131.         printf ( "%d\n", low - 1 );
  132.  
  133.     }
  134.  
  135.     return 0;
  136. }
  137.  
Success #stdin #stdout 0s 22944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R6lkje
Blog UVa 12430 - Grand Wedding
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!