| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 151275 |
2019-09-02T11:23:38 Z |
TadijaSebez |
Park (BOI16_park) |
C++11 |
|
69 ms |
2240 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});
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
2240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
