제출 #728000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728000		WonderfulWhale	Park (BOI16_park)	C++17	100 / 100	2366 ms	58456 KiB

park

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

struct drzewo {
	int x, y, r;
	drzewo() {}
	drzewo(int x, int y, int r):x(x), y(y), r(r) {}
};

int n, m, W, H;
int ans[4][4];

drzewo t[2009];
int Min[2009][2009];

vector<int> G[2009];
int num[2009];
int cur;

void dfs(int x, int z) {
	num[x] = z;
	for(int y:G[x]) if(num[y]==0) dfs(y, z);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> W >> H;
	for(int i=0;i<n;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		t[i] = drzewo(a, b, c);
	}
	for(int i=0;i<n;i++) {
		for(int j=i+1;j<n;j++) {
			int dis = (t[i].x-t[j].x)*(t[i].x-t[j].x)+(t[i].y-t[j].y)*(t[i].y-t[j].y);
			int s = -1;
			int e = 1e9/2;
			while(e-s>1) {
				int m = (e+s)/2;
				if((t[i].r+t[j].r+2*m)*(t[i].r+t[j].r+2*m)>dis) e = m;
				else s = m;
			}
			Min[i][j] = e;
			//cout << i << " " << j << " " << e << " lacz\n";
		}
	}
	//cout << "min end\n";
	for(int a=0;a<4;a++) {
		for(int b=a+1;b<4;b++) {
			//cout << "teraz: " << a << " " << b << "\n";
			int s = -1;
			int e = 1e9;
			while(e-s>1) {
				int m = (e+s)/2;
				//cout << "promien: " << m << "\n";
				for(int i=0;i<=n+4;i++) {
					G[i].clear();
				}
				for(int i=0;i<n;i++) {
					for(int j=i+1;j<n;j++) {
						if(Min[i][j] <= m) {
							//cout << "laczymy: " << i << " " << j << "\n";
							G[i].pb(j);
							G[j].pb(i);
						}
					}
				}
				for(int i=0;i<n;i++) {
					if(t[i].y-t[i].r-m < m) {
						//cout << i << " dol\n";
						G[n+1].pb(i);
						G[i].pb(n+1);
					}
					if(t[i].x-t[i].r-m < m) {
						//cout << i << " lewo\n";
						G[n].pb(i);
						G[i].pb(n);
					}
					if(t[i].x+t[i].r+m > W-m) {
						//cout << i << " prawo\n";
						G[n+2].pb(i);
						G[i].pb(n+2);
					}
					if(t[i].y+t[i].r+m > H-m) {
						//cout << i << " gora\n";
						G[n+3].pb(i);
						G[i].pb(n+3);
					}
				}
				memset(num, 0, sizeof(num));
				cur = 0;
				for(int i=0;i<n+4;i++) if(num[i]==0) dfs(i, ++cur);
				bool res = true;
				if(a%2 == b%2) {
					if(num[n+0] == num[n+2]) res = false;
					if(num[n+1] == num[n+3]) res = false;
				}
				if((a==0 and b==1) or (a==2 and b == 3)) {
					if(num[n+1]==num[n+3]) res = false;
				}
				if((a==0 and b==3) or (a==1 and b == 2)) {
					if(num[n]==num[n+2]) res = false;
				}
				if(num[n+a] == num[n+(a+1)%4]) res = false;
				if(num[n+b] == num[n+(b+1)%4]) res = false;
				if(res) s = m;
				else e = m;
			}
			//cout << a << " " << b << " " << s << "\n";
			ans[a][b] = s;
			ans[b][a] = s;
		}
	}
	for(int i=0;i<4;i++) {
		ans[i][i] = 2e9;
	}
	for(int i=0;i<m;i++) {
		int r, e;
		cin >> r >> e;
		e--;
		for(int j=0;j<4;j++) {
			if(ans[e][j] >= r) {
				cout << j+1;
			}
		}
		cout << "\n";
	}
}

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