| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 63838 |
2018-08-03T05:02:35 Z |
정원준(#1871) |
Park (BOI16_park) |
C++11 |
|
535 ms |
71996 KB |
#include <bits/stdc++.h>
#define L long long
#define dinf (1e12)
#define eps (1e-6)
#define double long double
using namespace std;
L n,m,w,h;
vector<L>v[2020];
vector<double>l[2020];
double adist[5][5];
L chk[2020],good[2020];
L col[2020][2020];
struct S{
L x,y,rad;
}a[2020];
struct E{
L s,e;
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;
}
L sq(L x){
return x*x;
}
double dist(L x,L y){
return sqrt((double)(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 %lld %lld",&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 %lld",&a[i].x,&a[i].y,&a[i].rad);
}
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
edgetop++;
edge[edgetop]=(E){i,j,dist(i,j)-(double)(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,(double)(a[i].x-a[i].rad)};
edgetop++;
edge[edgetop]=(E){i,n+2,(double)(a[i].y-a[i].rad)};
edgetop++;
edge[edgetop]=(E){i,n+3,(double)(w-a[i].x-a[i].rad)};
edgetop++;
edge[edgetop]=(E){i,n+4,(double)(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("");
}
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++)
{
adist[i][j]+=eps;
//printf("%lld %lld %lf\n",i,j,adist[i][j]);
}
//puts("");
}
//puts("!231231231231");
for(i=1;i<=m;i++)
{
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:72: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:173:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
park.cpp:217: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:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld %lld",&n,&m,&w,&h);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].rad);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:217:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%llf %lld",&rad,&st);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
469 ms |
64500 KB |
Output is correct |
| 2 |
Correct |
495 ms |
64808 KB |
Output is correct |
| 3 |
Correct |
474 ms |
64808 KB |
Output is correct |
| 4 |
Correct |
493 ms |
64808 KB |
Output is correct |
| 5 |
Correct |
468 ms |
64808 KB |
Output is correct |
| 6 |
Correct |
535 ms |
64808 KB |
Output is correct |
| 7 |
Correct |
500 ms |
71996 KB |
Output is correct |
| 8 |
Correct |
519 ms |
71996 KB |
Output is correct |
| 9 |
Correct |
3 ms |
71996 KB |
Output is correct |
| 10 |
Correct |
2 ms |
71996 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
84 ms |
71996 KB |
Output is correct |
| 2 |
Correct |
90 ms |
71996 KB |
Output is correct |
| 3 |
Incorrect |
70 ms |
71996 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
469 ms |
64500 KB |
Output is correct |
| 2 |
Correct |
495 ms |
64808 KB |
Output is correct |
| 3 |
Correct |
474 ms |
64808 KB |
Output is correct |
| 4 |
Correct |
493 ms |
64808 KB |
Output is correct |
| 5 |
Correct |
468 ms |
64808 KB |
Output is correct |
| 6 |
Correct |
535 ms |
64808 KB |
Output is correct |
| 7 |
Correct |
500 ms |
71996 KB |
Output is correct |
| 8 |
Correct |
519 ms |
71996 KB |
Output is correct |
| 9 |
Correct |
3 ms |
71996 KB |
Output is correct |
| 10 |
Correct |
2 ms |
71996 KB |
Output is correct |
| 11 |
Correct |
84 ms |
71996 KB |
Output is correct |
| 12 |
Correct |
90 ms |
71996 KB |
Output is correct |
| 13 |
Incorrect |
70 ms |
71996 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
