fork(1) download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5. " when you are not practicing someone else is ,
  6.  and the day u meet them u will lose "
  7. */
  8. #include<bits/stdc++.h>
  9. #include<stdio.h>
  10. using namespace std;
  11.  
  12. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  13. #define MAX 200005
  14.  
  15. #define ll long long
  16. #define ld long double
  17. #define lli long long int
  18.  
  19. #define pb push_back
  20. #define INF 1000000000000
  21. #define mod 1000000007
  22.  
  23. // trignometric function always give value in Radians only
  24. #define PI acos(-1) //3.1415926535897932384626433832795028
  25. #define dsin(degree) sin(degree*(PI/180.0))
  26. #define dcos(degree) cos(degree*(PI/180.0))
  27. #define dtan(degree) tan(degree*(PI/180.0))
  28.  
  29. #define rsin(radian) sin(radian)
  30. #define rcos(radian) cos(radian)
  31. #define rtan(radian) tan(radian)
  32.  
  33. #define mem0(a) memset(a,0,sizeof(a))
  34. #define mem1(a) memset(a,-1,sizeof(a))
  35. #define memf(a) memset(a,false,sizeof(a))
  36.  
  37. #define loop(i,n)  for (lli i = 0; i < n; i++)
  38. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  39.  
  40. #define all(v) v.begin(),v.end()
  41. #define rall(v) v.rbegin(),v.rend()
  42. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  43. #define sz(x) int(x.size())
  44. #define F first
  45. #define S second
  46.  
  47. #define mii map<lli,lli>
  48.  
  49. #define pii pair<lli,lli>
  50.  
  51. #define vi vector<lli>
  52. #define vvi vector<vi>
  53. #define vpi vector<pii>
  54. #define vbool vector<bool>
  55.  
  56. #define seti set<lli>
  57.  
  58. #define gcd(a,b) __gcd((a),(b))
  59. #define lcm(a,b) (a/gcd(a,b))*b
  60. #define abs(x) ((x < 0)?-(x):x)
  61.  
  62. #define endl '\n'
  63.  
  64. template <typename Head>
  65. void print(Head&& head)
  66. {
  67.     cout<<head<<endl;
  68. }
  69. template <typename Head, typename... Tail>
  70. void print(Head&& head, Tail... tail)
  71. {
  72.     cout<<head<<" ";
  73.     print(tail...);
  74. }
  75.  
  76. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  77. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  78.  
  79. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  80. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  81.  
  82. #define FD(N) fixed<<setprecision(N)
  83.  
  84. #define deb(x) cout<<#x<<" "<<x<<endl;
  85.  
  86. /*
  87. 1D vector -  vi dp(n,value);
  88. 2D vector -  vvi dp(n,vi(n,value));
  89. */
  90.  
  91. // chandan1,2
  92. void chandan1(){int y=1;return;}
  93. void chandan2(){
  94.         loop(i,10){
  95.         lli x=1;
  96.     }
  97.     return(chandan1());
  98. }
  99.  
  100. //-------------------------------------------------------------------DSU---------------------------------------------------------------
  101.  
  102. struct DSU
  103. {
  104.     static const int MAXN=100005;
  105.     lli parent[MAXN];
  106.     lli size[MAXN];
  107.  
  108.     //initialize all structures
  109.     DSU()
  110.     {
  111.         loop(i,MAXN)
  112.         {
  113.             parent[i]=i;
  114.             size[i]=1;
  115.         }
  116.     }
  117.  
  118.     // return the root(parent) of i (log *n) 
  119.     lli root(lli i)
  120.     {
  121.         while(parent[i]!=i)
  122.         {
  123.             parent[i] = parent[parent[i]];
  124.             i = parent[i];
  125.         }
  126.         return i;
  127.     }
  128.  
  129.  
  130.     // union of two nodes using path compression
  131.     void Union(lli a , lli b)
  132.     {
  133.         lli root_a = root(a);
  134.         lli root_b = root(b);
  135.  
  136.         if(root_a == root_b) return; // why we increase size then ?
  137.  
  138.         if(size[root_a] < size[root_b])
  139.         {
  140.             parent[root_a] = parent[root_b];
  141.             size[root_b] += size[root_a];
  142.         }
  143.  
  144.         else
  145.         {
  146.             parent[root_b] = parent[root_a];
  147.             size[root_a] += size[root_b];
  148.         }
  149.     }
  150.  
  151.     // check whether a and b are in same set (both have same root)
  152.     bool find(lli a , lli b)
  153.     {
  154.         return(a==b or root(a) == root(b));
  155.     }
  156.  
  157. };
  158.  
  159.  
  160. //-------------------------------------------------------------------DSU---------------------------------------------------------------
  161.  
  162. int main(){
  163. fastio
  164. lli t=1;
  165. //cin>>t;
  166. chandan2();
  167. while(t--) {
  168.     lli n,m,q;
  169.     cin>>n>>m;
  170.     vpi edges;
  171.     loop(i,m)
  172.     {
  173.         lli x,y;
  174.         cin>>x>>y;
  175.         edges.pb(make_pair(x,y));
  176.     }
  177.     lli val[n+1];
  178.     FOR(i,1,n+1)
  179.         cin>>val[i];
  180.     // FOR(i,1,n+1)
  181.     //     print(val[i]);
  182.     lli startNode , endNode;
  183.     cin>>startNode>>endNode;
  184.     lli s = 0 , e = 1e7 , ans;
  185.     while(s<=e)
  186.     {
  187.         lli mid = (s+e)/2;
  188.         DSU dsu;
  189.         for(auto xt : edges)
  190.         {
  191.             lli x = val[xt.F];
  192.             lli y = val[xt.S];
  193.             //print(x,y);
  194.             lli val = abs(x-y);
  195.             if(val<=mid)
  196.             {
  197.                 dsu.Union(xt.F,xt.S);
  198.             }
  199.         }
  200.  
  201.         if(dsu.find(startNode,endNode))
  202.         {
  203.             ans = mid;
  204.             e = mid-1;
  205.         }
  206.         else
  207.         {
  208.             s = mid+1;
  209.         }
  210.     }
  211.     print(ans);
  212.  
  213.   }
  214. return 0;
  215. }
Success #stdin #stdout 0.01s 5156KB
comments (?)
stdin
copy 
4 5
1 2
2 3
3 4
4 1
2 4
8 5 6 1
2 4
stdout
copy 
4
https://ideone.com/DBCFKQ
language:
C++ (gcc 8.3)
created:
3 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!