fork download
copy 
  1. /* Author: Ramandeep singh
  2.  panjab university, chandigarh
  3.  3rd sem
  4.  The_hawk_returns
  5.  Lets target expert on codeforces 
  6.  1.think of related algorithm don't sit quiet starring at the problem
  7.  2.Don't look at the leaderboard until you are done with the problems
  8.  
  9.   :) MAY THE FORCE BE WITH YOU  :)
  10.   
  11.  */
  12. #include <bits/stdc++.h>
  13. using namespace std;
  14.  
  15. #define watch(x)           cout<<(#x)<<"="<<(x)<<'\n'
  16. #define mset(d,val)         memset(d,val,sizeof(d))
  17. #define setp(x)             cout<<fixed<<setprecision(x)
  18. #define loop(i,a,b)         for(int i=(a);i<(b);i++)
  19. #define hunt(i,a,b)         for(int i=(a);i<=(b);i++)
  20. #define lp(i,a,b)           for(int i = a; i >= b; i--)
  21. #define rep(i,n)            for(int i = 0; i < n; i++)
  22. #define int                 long long int 
  23. #define boost    ios_base::sync_with_stdio(false); cin.tie(NULL);
  24. #define pb                  push_back
  25. #define f                   first
  26. #define s                   second
  27. #define pqueue              priority_queue
  28. #define fbo                 find_by_order
  29. #define ook                 order_of_key
  30. #define ll                  long long
  31. #define ii                  pair<int,int>
  32. #define vi                  vector<int>
  33. #define vii                 vector<ii>
  34. #define ld                  long double
  35. #define rd(n)              cin >> n  
  36. #define out(n)             cout << n <<endl  
  37. #define all(x)            begin(x),end(x)
  38. void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
  39. ll Bexp(ll a,int b){ ll ret=1; for (;b;a=a*a,b>>=1) if (b&1) ret=ret*a; return ret; }
  40. ll gcd(ll A , ll B)
  41. {
  42. 	if(B == 0)return A;
  43. 	return gcd(B , A%B);
  44. }
  45. ll min(ll a , ll b){return a > b ? b : a;}
  46. ll max(ll a , ll b){return a > b ? a : b;}
  47. #define MOD 1000000007
  48.  
  49. struct edge{
  50. 	int a;
  51. 	int b;
  52. 	int w;
  53. };
  54.  
  55. edge arr[1000011];
  56. int par[100001];
  57.  
  58. bool comp(edge a , edge b)
  59. {
  60. 	if(a.a < b.b)
  61. 		return true;
  62.  
  63. 	return false;
  64. }
  65.  
  66. int find(int a)
  67. {
  68. 	if(par[a] == -1)
  69. 		return a;
  70.  
  71. 	return par[a] = find(par[a]);
  72. }
  73.  
  74. void merge(int a , int b)
  75. {
  76. 	par[a] = b;
  77. }
  78.  
  79. bool ok(int n)
  80. {
  81. 	int x = find(1);
  82. 	int y = find(n);
  83.  
  84. 	if(x == y)
  85. 		return true;
  86. 	false;
  87. }
  88. signed main()
  89. {
  90.    boost
  91.  
  92.    #ifndef ONLINE_JUDGE
  93. 	freopen("input.txt", "r", stdin);
  94. 	freopen("output.txt", "w", stdout);
  95.    #endif
  96.  
  97.  
  98.     int t , n , m;
  99.  
  100.     cin >> t;
  101.     while(t--)
  102.     {
  103.     	cin >> n >> m;
  104.  
  105.     	for(int i = 1; i <= n; i++)
  106.     		par[i] = -1;
  107.  
  108.     	memset(arr , 0 , sizeof arr);
  109.  
  110.     	for(int i = 0; i < m; i++)
  111.     	{
  112.     		cin >> arr[i].a >> arr[i].b >> arr[i].w;
  113.     	}
  114.  
  115.     	sort(arr , arr+m ,comp);
  116.  
  117.     	//apply krushkal's algorithm .. 
  118.  
  119.         bool bul =true;
  120.  
  121.     	for(int i = 0; i < m; i++)
  122.     	{
  123.     		int a = find(arr[i].a);
  124.     		int b = find(arr[i].b);
  125.  
  126.     		if(a == b)
  127.     			continue;
  128.     		merge(a,b);
  129.  
  130.     		if(ok(n))
  131.     		{
  132.     			cout << arr[i].w << "\n";
  133.     			bul = true;
  134.     			break;
  135.     		}
  136.  
  137.     	}
  138.  
  139.     	if(!bul)
  140.     		cout << -1 << endl;
  141.  
  142.  
  143.  
  144.     }
  145. }
Time limit exceeded #stdin #stdout 5s 26824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z9JP1Y
problem MARYBMW, based on SPOJ submission 27468790 (C++ 4.3.2), 2021-02-23 06:29:52
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 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!