Submission #63837

# Submission time Handle Problem Language Result Execution time Memory
63837 2018-08-03T05:00:16 Z 정원준(#1871) Park (BOI16_park) C++11
27 / 100
386 ms 57032 KB
#include <bits/stdc++.h>
#define L long long
#define dinf (1e12)
#define eps (1e-8)
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("%lf %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:71: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:172:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<v[i].size();j++)
           ~^~~~~~~~~~~~
park.cpp:90: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:98: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:216:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf %lld",&rad,&st);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 386 ms 49016 KB Output is correct
2 Correct 364 ms 49516 KB Output is correct
3 Correct 356 ms 49516 KB Output is correct
4 Correct 384 ms 49516 KB Output is correct
5 Correct 367 ms 49516 KB Output is correct
6 Correct 368 ms 49516 KB Output is correct
7 Correct 309 ms 56864 KB Output is correct
8 Correct 309 ms 57032 KB Output is correct
9 Correct 5 ms 57032 KB Output is correct
10 Correct 4 ms 57032 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 68 ms 57032 KB Output is correct
2 Correct 66 ms 57032 KB Output is correct
3 Incorrect 78 ms 57032 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 386 ms 49016 KB Output is correct
2 Correct 364 ms 49516 KB Output is correct
3 Correct 356 ms 49516 KB Output is correct
4 Correct 384 ms 49516 KB Output is correct
5 Correct 367 ms 49516 KB Output is correct
6 Correct 368 ms 49516 KB Output is correct
7 Correct 309 ms 56864 KB Output is correct
8 Correct 309 ms 57032 KB Output is correct
9 Correct 5 ms 57032 KB Output is correct
10 Correct 4 ms 57032 KB Output is correct
11 Correct 68 ms 57032 KB Output is correct
12 Correct 66 ms 57032 KB Output is correct
13 Incorrect 78 ms 57032 KB Output isn't correct
14 Halted 0 ms 0 KB -