Submission #1096280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096280		boclobanchat	Park (BOI16_park)	C++14	100 / 100	482 ms	107604 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
struct edge { int l,r,d; };
struct point { int x,y,r; };
const int MAXN=2024;
const int sqr=1e5;
const int N=2345678;
point P[MAXN];
edge E[N];
int dsu[MAXN],F[5][5];
bool ck[5][5];
vector<edge> vi[sqr+5];
vector<ii> B[5][5];
int euclid(int x,int y,int u,int v)
{
	long long a=abs(x-u),b=abs(y-v),l=max(a,b),r=a+b,ans=0;
	while(l<=r)
	{
		long long mid=(l+r)/2;
		if(a*a+b*b>=mid*mid) l=mid+1,ans=mid;
		else r=mid-1;
	}
	return ans;
}
int root(int i)
{
	if(!dsu[i]) return i;
	return dsu[i]=root(dsu[i]);
}
void merge(int i,int j)
{
	if((i=root(i))==(j=root(j))) return ;
	dsu[j]=i;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,w,h,cnt=0;
    cin>>n>>m>>w>>h;
    B[1][2].push_back({1,2}),B[1][2].push_back({1,3}),B[1][2].push_back({1,4});
    B[1][3].push_back({1,3}),B[1][3].push_back({2,4}),B[1][3].push_back({1,4}),B[1][3].push_back({2,3});
    B[1][4].push_back({4,1}),B[1][4].push_back({4,2}),B[1][4].push_back({4,3});
    B[2][3].push_back({2,3}),B[2][3].push_back({2,4}),B[2][3].push_back({2,1});
    B[2][4].push_back({1,3}),B[2][4].push_back({2,4}),B[2][4].push_back({1,2}),B[2][4].push_back({3,4});
    B[3][4].push_back({3,4}),B[3][4].push_back({3,1}),B[3][4].push_back({3,2});
    for(int i=1;i<=n;i++)
    {
    	cin>>P[i].x>>P[i].y>>P[i].r;
    	E[++cnt]={1,i+4,P[i].y-P[i].r};
    	E[++cnt]={2,i+4,w-P[i].x-P[i].r};
    	E[++cnt]={3,i+4,h-P[i].y-P[i].r};
    	E[++cnt]={4,i+4,P[i].x-P[i].r};
	}
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) E[++cnt]={i+4,j+4,euclid(P[i].x,P[i].y,P[j].x,P[j].y)-P[i].r-P[j].r};
    for(int i=1;i<=cnt;i++) vi[E[i].d%sqr].push_back(E[i]);
    cnt=0;
    for(int i=0;i<=sqr;i++)
    {
    	for(auto v:vi[i]) E[++cnt]=v;
    	vi[i].clear();
	}
	for(int i=1;i<=cnt;i++) vi[E[i].d/sqr].push_back(E[i]);
    cnt=0;
    for(int i=0;i<=sqr;i++)
    {
    	for(auto v:vi[i]) E[++cnt]=v;
    	vi[i].clear();
	}
	for(int j=1;j<=4;j++) for(int k=1;k<=4;k++) F[j][k]=2e9*(j!=k);
	for(int i=1;i<=cnt;i++)
	{
		merge(E[i].l,E[i].r);
		for(int j=1;j<=4;j++) for(int k=j+1;k<=4;k++) if(!ck[j][k]&&root(j)==root(k)) ck[j][k]=true,F[j][k]=E[i].d;
	}
	for(int j=1;j<=4;j++) for(int k=j+1;k<=4;k++) F[k][j]=F[j][k],B[k][j]=B[j][k];
	for(int i=1;i<=m;i++)
	{
		int r,e;
		cin>>r>>e;
		r*=2;
		for(int j=1;j<=4;j++)
		{
			bool ck=true;
			for(auto v:B[j][e]) if(F[v.fi][v.se]<r) ck=false;
			if(ck) cout<<j;
		}
		cout<<"\n";
	}
}

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