Submission #1151524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151524		fyan	Park (BOI16_park)	C++20	0 / 100	264 ms	66464 KiB

park

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

namespace dsu {
	const int mxn = 2e3+5;
	
	int f[mxn];
	void build() {
		iota(f,f+mxn,0);
	}
	int trace(int v) {
		return (f[v]==v ? v : f[v] = trace(f[v]));
	}
	void unite(int u, int v) {
		if ((u = trace(u)) == (v = trace(v)))
			return;
		f[u] = v;
	}
};

const int mxn = 2e3+5;
const int mxq = 1e5+5;
const int inf = 4e18;

int n,m,w,h;
int x[mxn],y[mxn],r[mxn];
vector<array<int,4>> ord;
string ans[mxq];

/*
0 - bottom
1 - top
2 - left
3 - right
*/

int con(int a, int b) {
	//first radius that a intersects with b
	if (a > b) swap(a,b);
	if (a > 3) {
		//sqrt(difx^2 + dify^2) < ra+rb+2R
		int R = (sqrt((x[a]-x[b])*(x[a]-x[b]) + 
					  (y[a]-y[b])*(y[a]-y[b]))
				- r[a] - r[b])/2-2;
				
		R = max(R,0ll);
		while ((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b])
				>= (r[a]+r[b]+2*R)*(r[a]+r[b]+2*R)) R++;
		
		return R;
	}
	if (b > 3) {
		int dt;
		if (a==0) {dt = abs(y[b]-0);}
		if (a==1) {dt = abs(h-y[b]);}
		if (a==2) {dt = abs(x[b]-0);}
		if (a==3) {dt = abs(w-x[b]);}
		return (dt+1)/2;
	}
	return inf;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>m>>w>>h;
	for (int i=4; i<n+4; i++) {
		cin>>x[i]>>y[i]>>r[i];
	}
	ord.reserve((n+5)*(n+5)/2+mxq);
	for (int a=0; a<n+4; a++) {
		for (int b=a+1; b<n+4; b++) {
			ord.push_back({con(a,b),0,a,b});
		}
	}
	for (int i=0; i<m; i++) {
		int r,c; cin>>r>>c;
		ord.push_back({r,1,c,i});
	}
	sort(all(ord));
	dsu::build();
	for (auto [t,tp,a,b] : ord) {
		if (tp) {
			//current position is a
			int ok1=1,ok2=1,ok3=1,ok4=1;
			if (a==1) {
				if (dsu::trace(0)==dsu::trace(2)) ok2=ok3=ok4=0;
				if (dsu::trace(0)==dsu::trace(1)) ok2=ok3=0;
				if (dsu::trace(2)==dsu::trace(3)) ok3=ok4=0;
				if (dsu::trace(0)==dsu::trace(2)) ok1=0;
				if (dsu::trace(0)==dsu::trace(3)) ok2=0;
				if (dsu::trace(1)==dsu::trace(3)) ok3=0;
				if (dsu::trace(1)==dsu::trace(2)) ok4=0;
				ok1=1;
			}
			if (a==2) {
				if (dsu::trace(0)==dsu::trace(3)) ok1=ok3=ok4=0;
				if (dsu::trace(0)==dsu::trace(1)) ok1=ok4=0;
				if (dsu::trace(2)==dsu::trace(3)) ok3=ok4=0;
				if (dsu::trace(0)==dsu::trace(2)) ok1=0;
				if (dsu::trace(0)==dsu::trace(3)) ok2=0;
				if (dsu::trace(1)==dsu::trace(3)) ok3=0;
				if (dsu::trace(1)==dsu::trace(2)) ok4=0;
				ok2=1;
			}
			if (a==3) {
				if (dsu::trace(0)==dsu::trace(3)) ok1=ok2=ok4=0;
				if (dsu::trace(0)==dsu::trace(1)) ok1=ok4=0;
				if (dsu::trace(2)==dsu::trace(3)) ok1=ok2=0;
				if (dsu::trace(0)==dsu::trace(2)) ok1=0;
				if (dsu::trace(0)==dsu::trace(3)) ok2=0;
				if (dsu::trace(1)==dsu::trace(3)) ok3=0;
				if (dsu::trace(1)==dsu::trace(2)) ok4=0;
				ok3=1;
			}
			if (a==4) {
				if (dsu::trace(0)==dsu::trace(3)) ok1=ok2=ok3=0;
				if (dsu::trace(0)==dsu::trace(1)) ok2=ok3=0;
				if (dsu::trace(2)==dsu::trace(3)) ok1=ok2=0;
				if (dsu::trace(0)==dsu::trace(2)) ok1=0;
				if (dsu::trace(0)==dsu::trace(3)) ok2=0;
				if (dsu::trace(1)==dsu::trace(3)) ok3=0;
				if (dsu::trace(1)==dsu::trace(2)) ok4=0;
				ok3=1;
			}
			if (ok1) ans[b]+="1";
			if (ok2) ans[b]+="2";
			if (ok3) ans[b]+="3";
			if (ok4) ans[b]+="4";
			
//			cout<<"\n";
//			cout<<dsu::trace(0)<<" "<<dsu::trace(1)<<" "<<dsu::trace(2)<<" "<<dsu::trace(3)<<"\n";
//			cout<<t<<"  "<<a<<"\n";
//			cout<<"\n\n";
		} else {
			dsu::unite(a,b);
//			cout<<a<<" "<<b<<"\n";
		}
	}
	
	for (int i=0; i<m; i++)
		cout<<ans[i]<<"\n";
	
	
}

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