Submission #63838

# Submission time Handle Problem Language Result Execution time Memory
63838 2018-08-03T05:02:35 Z 정원준(#1871) Park (BOI16_park) C++11
27 / 100
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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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 -
# Verdict Execution time Memory 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 -