Advertisement
Guest User

Untitled

a guest
Jun 24th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3. using namespace std;
  4.  
  5. #define inf 1e9
  6. #define ll long long
  7. #define endl "\n"
  8. #define eps 1e-13
  9. vector<string> uva;
  10.  
  11.  
  12. ll n , m , k , d;
  13. ll parent[20000];
  14. ll siz[20000];
  15. pair<ll , ll> pos[20000];
  16.  
  17. void make_set(ll v)
  18. {
  19.     parent[v]=v;
  20.     siz[v]=(long long)1;
  21. }
  22. ll find_set(ll v)
  23. {
  24.     if(v==parent[v])
  25.         return v;
  26.     return parent[v]=find_set(parent[v]);
  27. }
  28. void union_set(ll a,ll b)
  29. {
  30.     a=find_set(a);
  31.     b=find_set(b);
  32.     if(a!=b)
  33.     {
  34.         if(siz[a] < siz[b])
  35.             swap(a,b);
  36.         parent[b]=a;
  37.         siz[a]+=siz[b];
  38.     }
  39. }
  40.  
  41. void join(ll node)
  42. {
  43.     for(ll i=(ll)0; i<node; i++)
  44.     {
  45.         if((pos[node].first-pos[i].first)*(pos[node].first-pos[i].first) + (pos[node].second-pos[i].second)*(pos[node].second-pos[i].second) <= k*k && i>=m)
  46.             union_set(node , i);
  47.         if((pos[node].first-pos[i].first)*(pos[node].first-pos[i].first) + (pos[node].second-pos[i].second)*(pos[node].second-pos[i].second) <= d*d && i<m)
  48.             union_set(node , i);
  49.     }
  50. }
  51.  
  52. int main()
  53. {
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(NULL), cout.tie(NULL);
  56.  
  57.     ll t;
  58.     cin>>t;
  59.     for(ll test=(ll)0; test<t; test++)
  60.     {
  61.         ll c=(ll)0;
  62.         cin>>n>>m>>k>>d;
  63.         for(ll i=(ll)0; i<m; i++)
  64.         {
  65.             ll x , y;
  66.             //cout<<"aaa"<<endl;
  67.             cin>>x>>y;
  68.             //cout<<"bbb"<<endl;
  69.             pos[i]=make_pair(x , y);
  70.             make_set(i);
  71.         }
  72.         c=m;
  73.         bool stop=false;
  74.         ll sick=(ll)0;
  75.         for(ll i=(ll)0; i<n; i++)
  76.         {
  77.             ll b;
  78.             cin>>b;
  79.             if(!stop)
  80.             {
  81.                 stop=true;
  82.                 sick=c+b;
  83.             }
  84.             ll x , y;
  85.             cin>>x>>y;
  86.             pos[c]=make_pair(x , y);
  87.             /*make_set(c);
  88.             join(c);
  89.             ll src=c;
  90.             c++;
  91.             for(ll j=(ll)1; j<b; j++)
  92.             {
  93.                 cin>>x>>y;
  94.                 pos[c]=make_pair(x,y);
  95.                 make_set(c);
  96.                 union_set(c , src);
  97.                 join(c);
  98.                 c++;
  99.             }*/
  100.         }
  101.         /*bool found=false;
  102.         for(ll i=(ll)0; i<m; i++)
  103.             for(ll j=m; j<sick; j++)
  104.                 if(find_set(i)==find_set(j) && !found)
  105.                 {
  106.                     uva.push_back("Tree can be saved :)");
  107.                     found=true;
  108.                 }
  109.         if(!found) uva.push_back("Tree can't be saved :(");*/
  110.     }
  111.     for(int i=0; i<uva.size(); i++)
  112.         cout<<uva[i]<<endl;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement