제출 #970610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970610		PM1	Park (BOI16_park)	C++17	100 / 100	801 ms	42784 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const int mxn=2e3+5,mxm=1e5+5,mxk=3e6,mm=1e9;
int n,m,comp[mxm],cnt=0,tnc=0,par[mxm],sz[mxm],hh,ww;
bool mark[mxm][5],now[7];
pair<int,int>node[mxm],q[mxm];
map<pair<int,int>,int>mp;
struct yall{
	int u,uu,w;
}yal[mxk];
vector<int>yl,qq,ans[mxm];
struct circle{
	int x,y,r;
}c[mxn];
bool cmp(int x,int y){
	return yal[x].w<yal[y].w;
}
bool cmp1(int x,int y){
	return q[x].fr>q[y].fr;
}
void ez(int x,int y){
	tnc++;
	yal[tnc].u=x;
	yal[tnc].uu=y;
	int r1=c[x].r,r2=(y>n)?0:c[y].r;
	ll xx=abs(node[x].fr-node[y].fr),yy=abs(node[x].sc-node[y].sc),dis=xx*xx+yy*yy;
	ll L=0,R=1e9;
	while(R-L>1){
		ll mid=(R+L)/2;
		if(mid*mid>dis)R=mid;
		else
			L=mid;
	}
	yal[tnc].w=(L-r1-r2)/2;
	yl.push_back(tnc);
}
void add(int x,int y,int i,int j){
	if(mp[make_pair(x,y)]==0){
		mp[make_pair(x,y)]=++cnt;
		node[cnt]=make_pair(x,y);
		par[cnt]=cnt;
		sz[cnt]=1;
		mark[cnt][j]=1;
	}
	ez(i,mp[make_pair(x,y)]);
}
void make_yal(){
	for(int i=1;i<=n;i++){
		par[i]=i;
		sz[i]=1;
		node[i]=make_pair(c[i].x,c[i].y);
		add(c[i].x,hh,i,3);
		add(c[i].x,0,i,1);
		add(ww,c[i].y,i,2);
		add(0,c[i].y,i,4);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ez(i,j);
		}
	}
	sort(yl.begin(),yl.end(),cmp);
}
int getpar(int x){
	return (par[x]==x)?x:par[x]=getpar(par[x]);
}
void dsu(int i){
	int x=yal[i].u,y=yal[i].uu;
	int z=getpar(x),w=getpar(y);
	if(z==w)return;
	if(sz[z]<sz[w])swap(z,w);
	par[w]=z;
	sz[z]+=sz[w];
	for(int j=1;j<=4;j++){
		mark[z][j]|=mark[w][j];
	}
	if(mark[z][1]&& mark[z][2]){
		now[1]=1;
		now[4]=1;
		now[5]=1;
	}
	if(mark[z][1]&& mark[z][3]){
		now[1]=1;
		now[2]=1;
		now[6]=1;
		now[5]=1;
	}
	if(mark[z][1]&& mark[z][4]){
		now[1]=1;
		now[2]=1;
		now[3]=1;
	}
	if(mark[z][2]&& mark[z][3]){
		now[2]=1;
		now[4]=1;
		now[6]=1;
	}
	if(mark[z][2]&& mark[z][4]){
		now[2]=1;
		now[3]=1;
		now[4]=1;
		now[5]=1;
	}
	if(mark[z][3]&& mark[z][4]){
		now[3]=1;
		now[6]=1;
		now[5]=1;
	}
}
void cal(ll x){
	while(qq.size() &&  q[qq.back()].fr<=x){
			int z=qq.back(),zz=q[z].sc;
			qq.pop_back();
			if(zz==1){
				ans[z].push_back(1);
				if(!now[1])
					ans[z].push_back(2);
				if(!now[2])
					ans[z].push_back(3);
				if(!now[3])
					ans[z].push_back(4);
			}
			if(zz==2){
				if(!now[1])
					ans[z].push_back(1);
				ans[z].push_back(2);
				if(!now[4])
					ans[z].push_back(3);
				if(!now[5])
					ans[z].push_back(4);
			}
			if(zz==3){
				if(!now[2])
					ans[z].push_back(1);
				if(!now[4])
					ans[z].push_back(2);
				ans[z].push_back(3);
				if(!now[6])
					ans[z].push_back(4);
			}
			if(zz==4){
				if(!now[3])
					ans[z].push_back(1);
				if(!now[5])
					ans[z].push_back(2);
				if(!now[6])
					ans[z].push_back(3);
				ans[z].push_back(4);
				
			}
		}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	cin>>ww>>hh;
	cnt=n;
	for(int i=1;i<=n;i++){
		cin>>c[i].x>>c[i].y>>c[i].r;
	}
	make_yal();
	for(int i=1;i<=m;i++){
		cin>>q[i].fr>>q[i].sc;
		qq.push_back(i);
	}
	sort(qq.begin(),qq.end(),cmp1);
	for(auto i:yl){
		cal(yal[i].w);
		dsu(i);
	}
	cal(1e18);
	for(int i=1;i<=m;i++){
		for(auto j:ans[i])cout<<j;
		cout<<'\n';
	}
}

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