oj.uz

Submission #970610

# Submission time Handle Problem Language Result Execution time Memory
970610 2024-04-26T19:24:16 Z PM1 Park (BOI16_park) C++17
100 / 100
 801 ms 42784 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 38040 KB Output is correct
2 Correct 705 ms 37848 KB Output is correct
3 Correct 711 ms 38240 KB Output is correct
4 Correct 695 ms 37992 KB Output is correct
5 Correct 689 ms 38084 KB Output is correct
6 Correct 707 ms 38332 KB Output is correct
7 Correct 527 ms 37580 KB Output is correct
8 Correct 510 ms 37552 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 2 ms 6580 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12320 KB Output is correct
2 Correct 47 ms 11820 KB Output is correct
3 Correct 55 ms 11732 KB Output is correct
4 Correct 46 ms 11720 KB Output is correct
5 Correct 48 ms 11816 KB Output is correct
6 Correct 51 ms 11796 KB Output is correct
7 Correct 38 ms 11728 KB Output is correct
8 Correct 37 ms 11620 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 38040 KB Output is correct
2 Correct 705 ms 37848 KB Output is correct
3 Correct 711 ms 38240 KB Output is correct
4 Correct 695 ms 37992 KB Output is correct
5 Correct 689 ms 38084 KB Output is correct
6 Correct 707 ms 38332 KB Output is correct
7 Correct 527 ms 37580 KB Output is correct
8 Correct 510 ms 37552 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 2 ms 6580 KB Output is correct
11 Correct 59 ms 12320 KB Output is correct
12 Correct 47 ms 11820 KB Output is correct
13 Correct 55 ms 11732 KB Output is correct
14 Correct 46 ms 11720 KB Output is correct
15 Correct 48 ms 11816 KB Output is correct
16 Correct 51 ms 11796 KB Output is correct
17 Correct 38 ms 11728 KB Output is correct
18 Correct 37 ms 11620 KB Output is correct
19 Correct 801 ms 42664 KB Output is correct
20 Correct 764 ms 42528 KB Output is correct
21 Correct 791 ms 42784 KB Output is correct
22 Correct 799 ms 42712 KB Output is correct
23 Correct 759 ms 42672 KB Output is correct
24 Correct 560 ms 42412 KB Output is correct