| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 63855 |
2018-08-03T05:26:12 Z |
정원준(#1871) |
Park (BOI16_park) |
C++11 |
|
641 ms |
72532 KB |
#include <bits/stdc++.h>
#define L long long
#define dinf (1e12)
#define eps (1e-6)
using namespace std;
L n,m;
long double w,h;
vector<L>v[2020];
vector<long double>l[2020];
long double adist[5][5];
L chk[2020],good[2020];
L col[2020][2020];
struct S{
L x,y;
long double rad;
}a[2020];
struct E{
L s,e;
long double dist;
}edge[5000000];
L edgetop;
bool operator<(E a,E b){
return a.dist<b.dist;
}
L bu[2020];
L fin(L x){
return bu[x]==x?x:bu[x]=fin(bu[x]);
}
void uni(L x,L y){
x=fin(x);
y=fin(y);
bu[x]=y;
}
long double sq(long double x){
return x*x;
}
long double dist(L x,L y){
return sqrt((sq(a[x].x-a[y].x)+sq(a[x].y-a[y].y)));
}
L bit(L x){
L ret=0;
while(x)
{
ret+=x%2;
x/=2;
}
return ret;
}
L ord(L x){
L ret=-1;
while(x)
{
ret++;
x/=2;
}
return ret;
}
void dfs(L x,L num){
L i;
for(i=0;i<v[x].size();i++)
{
if(!chk[v[x][i]])
{
chk[v[x][i]]=1;
dfs(v[x][i],num);
if(good[v[x][i]])
{
//printf("%lld %lld %lld\n",x,v[x][i],num);
good[x]=1;
col[x][v[x][i]]|=(1<<num);
col[v[x][i]][x]|=(1<<num);
}
}
}
}
int main()
{
scanf("%lld %lld %llf %llf",&n,&m,&w,&h);
L i,j,k;
for(i=1;i<=4;i++)
{
adist[i][i]=dinf;
}
for(i=1;i<=n;i++)
{
scanf("%lld %lld %llf",&a[i].x,&a[i].y,&a[i].rad);
a[i].rad-=eps;
}
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
edgetop++;
edge[edgetop]=(E){i,j,dist(i,j)-(a[i].rad+a[j].rad)};
}
}
for(i=1;i<=n+4;i++)
{
bu[i]=i;
}
for(i=1;i<=n;i++)
{
edgetop++;
edge[edgetop]=(E){i,n+1,(a[i].x-a[i].rad)};
edgetop++;
edge[edgetop]=(E){i,n+2,(a[i].y-a[i].rad)};
edgetop++;
edge[edgetop]=(E){i,n+3,(w-a[i].x-a[i].rad)};
edgetop++;
edge[edgetop]=(E){i,n+4,(h-a[i].y-a[i].rad)};
}
sort(edge+1,edge+edgetop+1);
//printf("%lld\n",edgetop);
for(i=1;i<=edgetop;i++)
{
if(fin(edge[i].s)!=fin(edge[i].e))
{
//printf("%lld %lld\n",edge[i].s,edge[i].e);
v[edge[i].s].push_back(edge[i].e);
v[edge[i].e].push_back(edge[i].s);
l[edge[i].s].push_back(edge[i].dist);
l[edge[i].e].push_back(edge[i].dist);
uni(edge[i].s,edge[i].e);
}
}
for(i=1;i<=n+4;i++)
{
chk[i]=good[i]=0;
}
chk[n+1]=1;
good[n+2]=1;
dfs(n+1,1);
for(i=1;i<=n+4;i++)
{
chk[i]=good[i]=0;
}
chk[n+2]=1;
good[n+3]=1;
dfs(n+2,2);
for(i=1;i<=n+4;i++)
{
chk[i]=good[i]=0;
}
chk[n+3]=1;
good[n+4]=1;
dfs(n+3,3);
for(i=1;i<=n+4;i++)
{
chk[i]=good[i]=0;
}
chk[n+4]=1;
good[n+1]=1;
dfs(n+4,4);
for(i=1;i<=n+4;i++)
{
//printf("%lld\n",i);
for(j=0;j<v[i].size();j++)
{
//printf("%lld %lld ",v[i][j],col[i][v[i][j]]);
L temp=col[i][v[i][j]];
if(bit(temp)==2)
{
L st=temp&-temp;
temp^=st;
L ed=temp&-temp;
st=ord(st);
ed=ord(ed);
adist[st][ed]=max(adist[st][ed],l[i][j]);
adist[ed][st]=max(adist[ed][st],l[i][j]);
}
}
//puts("");
}
L loop=4;
while(loop--)
{
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
for(k=1;k<=4;k++)
{
if(adist[i][j]<min(adist[i][k],adist[k][j]))
{
adist[i][j]=min(adist[i][k],adist[k][j]);
}
}
}
}
}
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
//printf("%lld %lld %lf\n",i,j,(double)adist[i][j]);
}
//puts("");
}
//puts("!231231231231");
for(i=1;i<=m;i++)
{
long double rad;
L st;
scanf("%llf %lld",&rad,&st);
for(j=1;j<=4;j++)
{
if(adist[st][j]>=rad*2) printf("%lld",j);
}
puts("");
}
}
Compilation message
park.cpp: In function 'void dfs(long long int, long long int)':
park.cpp:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:93:41: warning: use of 'll' length modifier with 'f' type character has either no effect or undefined behavior [-Wformat=]
scanf("%lld %lld %llf %llf",&n,&m,&w,&h);
^
park.cpp:93:41: warning: use of 'll' length modifier with 'f' type character has either no effect or undefined behavior [-Wformat=]
park.cpp:101:51: warning: use of 'll' length modifier with 'f' type character has either no effect or undefined behavior [-Wformat=]
scanf("%lld %lld %llf",&a[i].x,&a[i].y,&a[i].rad);
^
park.cpp:176:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
park.cpp:223:29: warning: use of 'll' length modifier with 'f' type character has either no effect or undefined behavior [-Wformat=]
scanf("%llf %lld",&rad,&st);
^
park.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %llf %llf",&n,&m,&w,&h);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %llf",&a[i].x,&a[i].y,&a[i].rad);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:223:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%llf %lld",&rad,&st);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
507 ms |
64504 KB |
Output is correct |
| 2 |
Correct |
515 ms |
64812 KB |
Output is correct |
| 3 |
Correct |
509 ms |
64812 KB |
Output is correct |
| 4 |
Correct |
537 ms |
64812 KB |
Output is correct |
| 5 |
Correct |
515 ms |
64812 KB |
Output is correct |
| 6 |
Correct |
498 ms |
64812 KB |
Output is correct |
| 7 |
Correct |
489 ms |
72252 KB |
Output is correct |
| 8 |
Correct |
483 ms |
72252 KB |
Output is correct |
| 9 |
Correct |
5 ms |
72252 KB |
Output is correct |
| 10 |
Correct |
3 ms |
72252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
72252 KB |
Output is correct |
| 2 |
Correct |
83 ms |
72252 KB |
Output is correct |
| 3 |
Correct |
86 ms |
72252 KB |
Output is correct |
| 4 |
Correct |
81 ms |
72252 KB |
Output is correct |
| 5 |
Correct |
63 ms |
72252 KB |
Output is correct |
| 6 |
Correct |
87 ms |
72252 KB |
Output is correct |
| 7 |
Correct |
69 ms |
72252 KB |
Output is correct |
| 8 |
Correct |
85 ms |
72252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
507 ms |
64504 KB |
Output is correct |
| 2 |
Correct |
515 ms |
64812 KB |
Output is correct |
| 3 |
Correct |
509 ms |
64812 KB |
Output is correct |
| 4 |
Correct |
537 ms |
64812 KB |
Output is correct |
| 5 |
Correct |
515 ms |
64812 KB |
Output is correct |
| 6 |
Correct |
498 ms |
64812 KB |
Output is correct |
| 7 |
Correct |
489 ms |
72252 KB |
Output is correct |
| 8 |
Correct |
483 ms |
72252 KB |
Output is correct |
| 9 |
Correct |
5 ms |
72252 KB |
Output is correct |
| 10 |
Correct |
3 ms |
72252 KB |
Output is correct |
| 11 |
Correct |
82 ms |
72252 KB |
Output is correct |
| 12 |
Correct |
83 ms |
72252 KB |
Output is correct |
| 13 |
Correct |
86 ms |
72252 KB |
Output is correct |
| 14 |
Correct |
81 ms |
72252 KB |
Output is correct |
| 15 |
Correct |
63 ms |
72252 KB |
Output is correct |
| 16 |
Correct |
87 ms |
72252 KB |
Output is correct |
| 17 |
Correct |
69 ms |
72252 KB |
Output is correct |
| 18 |
Correct |
85 ms |
72252 KB |
Output is correct |
| 19 |
Correct |
641 ms |
72252 KB |
Output is correct |
| 20 |
Correct |
594 ms |
72252 KB |
Output is correct |
| 21 |
Correct |
598 ms |
72252 KB |
Output is correct |
| 22 |
Correct |
523 ms |
72252 KB |
Output is correct |
| 23 |
Correct |
550 ms |
72252 KB |
Output is correct |
| 24 |
Correct |
508 ms |
72532 KB |
Output is correct |
