oj.uz

Submission #151268

# Submission time Handle Problem Language Result Execution time Memory
151268 2019-09-02T11:14:05 Z TadijaSebez Park (BOI16_park) C++11
27 / 100
 74 ms 3312 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 632 KB Output is correct
2 Correct 19 ms 504 KB Output is correct
3 Correct 15 ms 376 KB Output is correct
4 Correct 16 ms 476 KB Output is correct
5 Correct 16 ms 504 KB Output is correct
6 Correct 16 ms 504 KB Output is correct
7 Correct 41 ms 484 KB Output is correct
8 Correct 16 ms 504 KB Output is correct
9 Correct 2 ms 408 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 632 KB Output is correct
2 Correct 19 ms 504 KB Output is correct
3 Correct 15 ms 376 KB Output is correct
4 Correct 16 ms 476 KB Output is correct
5 Correct 16 ms 504 KB Output is correct
6 Correct 16 ms 504 KB Output is correct
7 Correct 41 ms 484 KB Output is correct
8 Correct 16 ms 504 KB Output is correct
9 Correct 2 ms 408 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 74 ms 3312 KB Output isn't correct
12 Halted 0 ms 0 KB -