Submission #64419

#	Time	Username	Problem	Language	Result	Execution time	Memory
64419		zetapi	Park (BOI16_park)	C++14	100 / 100	1373 ms	63396 KiB

park

#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 
 
typedef pair<int,int> pii;
 
const int MAX=1e5;
const int INF=1e9;
 
struct data
{
	int X;
	int Y;
	int R;
} 	Circle[MAX],People[MAX];
 
vector<pair<int,pii>> edges;
 
vector<int> res[MAX];
 
int N,M,W,H,par[MAX],order[MAX],ranks[MAX];
 
int sq(int f)
{
	return f*f;
}
 
bool ok(int f,int s,int r)
{
	if(s>=N)
	{
		switch(s-N)
		{
			case 0: return Circle[f].Y-Circle[f].R-2*r>=0;;
			case 1: return Circle[f].X+Circle[f].R+2*r<=W;
			case 2: return Circle[f].Y+Circle[f].R+2*r<=H;
			case 3: return Circle[f].X-Circle[f].R-2*r>=0;
		}
	}
	return sq(Circle[f].X-Circle[s].X)+sq(Circle[f].Y-Circle[s].Y)>=sq(Circle[f].R+Circle[s].R+2*r);
}
 
int find(int f,int s)
{
	int low=0,high=INF,mid,res=0;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(ok(f,s,mid))
		{
			res=mid;
			low=mid+1;
		}
		else
			high=mid-1;
	}
	return res;
}
 
int root(int X)
{
	if(par[X]==X)
		return X;
	return par[X]=root(par[X]);
}
 
void unions(int X,int Y)
{
	int u=root(X),v=root(Y);
	if(ranks[u]>ranks[v])
		swap(u,v);
	par[u]=v;
	ranks[u]+=ranks[u]==ranks[v];
	return ;
}
 
bool cmp(int f,int s)
{
	return People[f].R<People[s].R;
}
 
int pre(int X)
{
	return (X-1+4)%4;
}
 
int next(int X)
{
	return (X+1+4)%4;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
 
	cin>>N>>M;
	cin>>W>>H;
	for(int A=0;A<N;A++)
		cin>>Circle[A].X>>Circle[A].Y>>Circle[A].R;
	for(int A=0;A<M;A++)
	{
		cin>>People[A].R>>People[A].X;
		People[A].X--;
		order[A]=A;
	}
	for(int A=0;A<N;A++)
		for(int B=A+1;B<N+4;B++)
			edges.pb(mp(find(A,B),mp(A,B)));
	sort(edges.begin(),edges.end());
	sort(order,order+M,cmp);
	for(int A=0;A<N+4;A++)
		par[A]=A;
	int ptr=0;
	for(int A=0;A<M;A++)
	{
		//cout<<order[A]<<" ha ha\n";
		while(ptr<edges.size() and edges[ptr].first<People[order[A]].R)
		{
			//cout<<edges[ptr].second.first<<" edges  "<<edges[ptr].second.second<<" limit is "<<edges[ptr].first<<"\n";
			unions(edges[ptr].second.first,edges[ptr].second.second);
			++ptr;
		}
		//cout<<ptr<<"\n";
		int corner=People[order[A]].X;
		int previous=pre(corner);
		int f_0=corner;
		int f_1=next(f_0);
		int f_2=next(f_1);
		int f_3=next(f_2);
		corner+=N;
		previous+=N;
		f_0+=N;
		f_1+=N;
		f_2+=N;
		f_3+=N;
		//cout<<f_0<<" "<<f_1<<" "<<f_2<<" "<<f_3<<"\n";
		//cout<<root(f_0)<<" "<<root(f_1)<<" "<<root(f_2)<<" "<<root(f_3)<<"\n";
		if(root(previous)!=root(corner) and root(corner)!=root(f_1) and root(f_0)!=root(f_2))
			res[order[A]].pb(f_1-N);
		if(root(previous)!=root(corner) and root(f_1)!=root(f_2) and root(previous)!=root(f_1) and root(corner)!=root(f_2))
			res[order[A]].pb(f_2-N);
		if(root(previous)!=root(corner) and root(f_2)!=root(f_3) and root(previous)!=root(f_1))
			res[order[A]].pb(f_3-N);
	}
	for(int A=0;A<M;A++)
	{
		res[A].pb(People[A].X);
		sort(res[A].begin(),res[A].end());
		for(auto B:res[A])
			cout<<B+1;
		cout<<"\n";
	}
	return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:121:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<edges.size() and edges[ptr].first<People[order[A]].R)
         ~~~^~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42