Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <stdio.h>
- using namespace std;
- #define inf 1e9
- #define ll long long
- #define endl "\n"
- #define eps 1e-13
- vector<string> uva;
- ll n , m , k , d;
- ll parent[20000];
- ll siz[20000];
- pair<ll , ll> pos[20000];
- void make_set(ll v)
- {
- parent[v]=v;
- siz[v]=(long long)1;
- }
- ll find_set(ll v)
- {
- if(v==parent[v])
- return v;
- return parent[v]=find_set(parent[v]);
- }
- void union_set(ll a,ll b)
- {
- a=find_set(a);
- b=find_set(b);
- if(a!=b)
- {
- if(siz[a] < siz[b])
- swap(a,b);
- parent[b]=a;
- siz[a]+=siz[b];
- }
- }
- void join(ll node)
- {
- for(ll i=(ll)0; i<node; i++)
- {
- 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)
- union_set(node , i);
- 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)
- union_set(node , i);
- }
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(NULL), cout.tie(NULL);
- ll t;
- cin>>t;
- for(ll test=(ll)0; test<t; test++)
- {
- ll c=(ll)0;
- cin>>n>>m>>k>>d;
- for(ll i=(ll)0; i<m; i++)
- {
- ll x , y;
- //cout<<"aaa"<<endl;
- cin>>x>>y;
- //cout<<"bbb"<<endl;
- pos[i]=make_pair(x , y);
- make_set(i);
- }
- c=m;
- bool stop=false;
- ll sick=(ll)0;
- for(ll i=(ll)0; i<n; i++)
- {
- ll b;
- cin>>b;
- if(!stop)
- {
- stop=true;
- sick=c+b;
- }
- ll x , y;
- cin>>x>>y;
- pos[c]=make_pair(x , y);
- /*make_set(c);
- join(c);
- ll src=c;
- c++;
- for(ll j=(ll)1; j<b; j++)
- {
- cin>>x>>y;
- pos[c]=make_pair(x,y);
- make_set(c);
- union_set(c , src);
- join(c);
- c++;
- }*/
- }
- /*bool found=false;
- for(ll i=(ll)0; i<m; i++)
- for(ll j=m; j<sick; j++)
- if(find_set(i)==find_set(j) && !found)
- {
- uva.push_back("Tree can be saved :)");
- found=true;
- }
- if(!found) uva.push_back("Tree can't be saved :(");*/
- }
- for(int i=0; i<uva.size(); i++)
- cout<<uva[i]<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement