Submission #63848

# Submission time Handle Problem Language Result Execution time Memory
63848 2018-08-03T05:17:03 Z 정원준(#1871) Park (BOI16_park) C++11
0 / 100
519 ms 72064 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 475 ms 64632 KB Output is correct
2 Correct 465 ms 64816 KB Output is correct
3 Correct 469 ms 64816 KB Output is correct
4 Correct 462 ms 64816 KB Output is correct
5 Correct 519 ms 64816 KB Output is correct
6 Correct 475 ms 64816 KB Output is correct
7 Correct 476 ms 72064 KB Output is correct
8 Incorrect 432 ms 72064 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 72 ms 72064 KB Output is correct
2 Correct 81 ms 72064 KB Output is correct
3 Incorrect 62 ms 72064 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 475 ms 64632 KB Output is correct
2 Correct 465 ms 64816 KB Output is correct
3 Correct 469 ms 64816 KB Output is correct
4 Correct 462 ms 64816 KB Output is correct
5 Correct 519 ms 64816 KB Output is correct
6 Correct 475 ms 64816 KB Output is correct
7 Correct 476 ms 72064 KB Output is correct
8 Incorrect 432 ms 72064 KB Output isn't correct
9 Halted 0 ms 0 KB -