Submission #1126586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126586		nguyenphong233	Park (BOI16_park)	C++20	100 / 100	438 ms	69288 KiB

park

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long 
#define double long double
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,m,w,h;
struct node{
	int r,e,id;
}a[MAX];
struct cir{
	int x,y,r;
}b[MAX];
string s[MAX];
vector<pair<double,ii>> cost;
int par[MAX];
int find(int u){
	return (u == par[u] ? u : par[u] = find(par[u]));
}
void dsu(int u,int v){
	int x = find(u);
	int y = find(v);
	if(x == y)return;
	par[x] = y;
}
bool onec(int u,int v){
	int x = find(u);
	int y = find(v);
	return (x == y);
}
signed main(){	
	
	read();
	cin >> n >> m >> w >> h;
	
	for(int i = 1;i <= n + 5;i++)par[i] = i;	
	for(int i = 1,x,y,r;i <= n;i++){
		cin >> x >> y >> r;
		b[i] = {x,y,r};
		for(int j = 1;j < i;j++){
			cost.push_back({sqrt((x - b[j].x) * (x - b[j].x) + (y - b[j].y) * (y - b[j].y)) - r - b[j].r,{i,j}});
		}
		cost.push_back({h - (y + r),{i,n + 1}});
		cost.push_back({y - r,{i,n + 3}});
		cost.push_back({w - (x + r),{i,n + 2}});
		cost.push_back({x - r,{i,n + 4}});
	}
	
	sort(cost.begin(),cost.end());
	
	for(int i = 1,r,e;i <= m;i++){
		cin >> r >> e;
		a[i] = {r,e,i};
	}
	//for(auto v : cost)cout << v.X << " " << v.Y.X << " " << v.Y.Y << '\n';
	sort(a + 1,a + 1 + m,[&](const node &a,const node &b){
		return a.r < b.r;
	});
	
	int t = -1;
	for(int i = 1;i <= m;i++){
		double r = a[i].r * 2.00;
		int e = a[i].e;
		int id = a[i].id;
		
		while(t + 1 < (int)cost.size() && cost[t + 1].X < r){
			t++;
			dsu(cost[t].Y.X,cost[t].Y.Y);
		}
		
		//cout << id << ' ' << r << " " << e << '\n';
		s[id] = "";
		if(e == 1){
			s[id] += "1";
			if(!onec(n + 1,n + 3) && !onec(n + 3,n + 2) && !onec(n + 4,n + 3))s[id] += "2";
			if(!onec(n + 1,n + 2) && !onec(n + 3,n + 1) && !onec(n + 4,n + 2) && !onec(n + 4,n + 3))s[id] += "3";
			if(!onec(n + 1,n + 4) && !onec(n + 4,n + 3) && !onec(n + 4,n + 2))s[id] += "4";
		}else if(e == 2){
			if(!onec(n + 1,n + 3) && !onec(n + 3,n + 2) && !onec(n + 4,n + 3))s[id] += "1";
			s[id] += "2";
			if(!onec(n + 2,n + 3) && !onec(n + 4,n + 2) && !onec(n + 1,n + 2))s[id] += "3";
			if(!onec(n + 4,n + 2) && !onec(n + 1,n + 3) && !onec(n + 4,n + 1) && !onec(n + 3,n + 2))s[id] += "4";
		}else if(e == 3){
			if(!onec(n + 1,n + 2) && !onec(n + 3,n + 1) && !onec(n + 4,n + 2) && !onec(n + 4,n + 3))s[id] += "1";
			if(!onec(n + 2,n + 3) && !onec(n + 4,n + 2) && !onec(n + 1,n + 2))s[id] += "2";
			s[id] += "3";
			if(!onec(n + 1,n + 4) && !onec(n + 1,n + 2) && !onec(n + 1,n + 3))s[id] += "4";
		}else if(e == 4){
			if(!onec(n + 1,n + 4) && !onec(n + 4,n + 3) && !onec(n + 4,n + 2))s[id] += "1";
			if(!onec(n + 4,n + 2) && !onec(n + 1,n + 3) && !onec(n + 4,n + 1) && !onec(n + 3,n + 2))s[id] += "2";
			if(!onec(n + 1,n + 4) && !onec(n + 1,n + 2) && !onec(n + 1,n + 3))s[id] += "3";
			s[id] += "4";
		}
	}
	for(int i = 1;i <= m;i++)cout << s[i] << '\n';
}

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