Submission #151268

#	Time	Username	Problem	Language	Result	Execution time	Memory
151268		TadijaSebez	Park (BOI16_park)	C++11	27 / 100	74 ms	3312 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=2005;
const int M=100050;
ll sq(ll x, ll y){ return x*x+y*y;}
struct Circle
{
	ll x,y,r;
	Circle(){}
	Circle(ll a, ll b, ll c):x(a),y(b),r(c){}
	bool Check(Circle b, ll d)
	{
		return sq(d+r+b.r,0)>sq(x-b.x,y-b.y);
	}
} C[N];
vector<pair<int,int>> Qs[5];
struct DSU
{
	int p[N];
	void init(){ for(int i=0;i<N;i++) p[i]=i;}
	DSU(){ init();}
	int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
	void Union(int x, int y){ p[Find(x)]=Find(y);}
	bool Same(int x, int y){ return Find(x)==Find(y);}
} DS;
int n,m,h,w;
bool Check(int e, int f)
{
	if(e>f) swap(e,f);
	if(e==1)
	{
		if(DS.Same(n+1,n+4)) return 1;
		if(f==2) return DS.Same(n+1,n+2) || DS.Same(n+1,n+3);
		if(f==3) return DS.Same(n+1,n+3) || DS.Same(n+4,n+2);
		if(f==4) return DS.Same(n+4,n+2) || DS.Same(n+4,n+3);
	}
	if(e==2)
	{
		if(DS.Same(n+1,n+2)) return 1;
		if(f==3) return DS.Same(n+2,n+3) || DS.Same(n+2,n+4);
		if(f==4) return DS.Same(n+1,n+3) || DS.Same(n+2,n+4);
	}
	if(e==3)
	{
		if(DS.Same(n+2,n+3)) return 1;
		if(f==4) return DS.Same(n+3,n+4) || DS.Same(n+3,n+1);
	}
}
bool ans[M][5];
int main()
{
	scanf("%i %i",&n,&m);
	scanf("%i %i",&w,&h);
	for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&C[i].x,&C[i].y,&C[i].r);
	for(int i=1,e,r;i<=m;i++) scanf("%i %i",&r,&e),Qs[e].pb({r,i});
	auto BuildGraph=[&](int r)
	{
		DS.init();
		//printf("R:%i ",r);
		for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(C[i].Check(C[j],r*2)) DS.Union(i,j);
		for(int i=1;i<=n;i++)
		{
			if(C[i].y<(ll)C[i].r+r*2) DS.Union(n+1,i);
			if(h-C[i].y<(ll)C[i].r+r*2) DS.Union(n+3,i);
			if(C[i].x<(ll)C[i].r+r*2) DS.Union(n+4,i);
			if(w-C[i].x<(ll)C[i].r+r*2) DS.Union(n+2,i);
		}
		//printf("\n");
	};
	for(int e=1;e<=4;e++)
	{
		sort(Qs[e].begin(),Qs[e].end());
		//for(int i=0;i<Qs[e].size();i++) printf("%i %i\n",Qs[e][i].first,Qs[e][i].second);
		for(int f=1;f<=4;f++)
		{
			int top=(int)Qs[e].size()-1,bot=0,mid,ans=-1;
			if(f!=e)
			{
				while(top>=bot)
				{
					mid=top+bot>>1;
					BuildGraph(Qs[e][mid].first);
					if(!Check(e,f)) ans=mid,bot=mid+1;
					else top=mid-1;
				}
			}
			else ans=(int)Qs[e].size()-1;
			for(int i=0;i<=ans;i++) ::ans[Qs[e][i].second][f]=1;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=4;j++) if(ans[i][j]) printf("%i",j);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
park.cpp: In function 'bool Check(int, int)':
park.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
park.cpp: In function 'int main()':
park.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
park.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&w,&h);
  ~~~~~^~~~~~~~~~~~~~~
park.cpp:56:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&C[i].x,&C[i].y,&C[i].r);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:57:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1,e,r;i<=m;i++) scanf("%i %i",&r,&e),Qs[e].pb({r,i});
                            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42