Submission #437100

#	Time	Username	Problem	Language	Result	Execution time	Memory
437100		penguinhacker	Park (BOI16_park)	C++14	100 / 100	382 ms	29764 KiB

park

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

#define ll long long
#define ar array

const int mxN=2000, mxM=1e5;
int n, m, w, h, p[mxN+4];
vector<ar<int, 3>> edges;
ar<int, 3> visitors[mxM];
string ans[mxM];
bool vis[4], bad[4][4];

struct circ {
	int x, y, r;
} c[mxN];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

void dfs(int u) {
	vis[u]=1;
	for (int v=0; v<4; ++v)
		if (!vis[v]&&!bad[u][v])
			dfs(v);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> w >> h;
	for (int i=0; i<n; ++i)
		cin >> c[i].x >> c[i].y >> c[i].r;
	edges.reserve(4*n+n*(n-1)/2);
	for (int i=0; i<n; ++i) {
		for (int j=i+1; j<n; ++j) {
			ll x=c[i].x-c[j].x;
			ll y=c[i].y-c[j].y;
			ll d=sqrt(x*x+y*y)-1;
			while((d+1)*(d+1)<=x*x+y*y)
				++d;
			int d2=d-c[i].r-c[j].r;
			edges.push_back({d2, i+4, j+4});
		}
		edges.push_back({c[i].y-c[i].r, 0, i+4}); // down
		edges.push_back({w-c[i].x-c[i].r, 1, i+4}); // right
		edges.push_back({h-c[i].y-c[i].r, 2, i+4}); // up
		edges.push_back({c[i].x-c[i].r, 3, i+4}); // left
	}
	for (int i=0; i<m; ++i) {
		int r, t;
		cin >> r >> t, --t;
		visitors[i]={r, t, i};
	}
	sort(edges.rbegin(), edges.rend());
	sort(visitors, visitors+m);
	iota(p, p+n+4, 0);
	for (int i=0; i<m; ++i) {
		while(edges.size()&&edges.back()[0]<2*visitors[i][0]) {
			//cout << edges.back()[0] << " " << edges.back()[1] << " " << edges.back()[2] << endl;
			int u=find(edges.back()[1]), v=find(edges.back()[2]);
			//cout << i << " " << u << " " << v << endl;
			p[v]=u;
			edges.pop_back();
		}
		for (int j=0; j<4; ++j) {
			int nxt=(j+1)%4;
			if (find(j)==find(nxt))
				for (int k=2; k<=4; ++k)
					bad[nxt][(j+k)%4]=bad[(j+k)%4][nxt]=1;
			if (find(j)==find((j+2)%4))
				for (int k1 : {j, (j+3)%4})
					for (int k2 : {nxt, (j+2)%4})
						bad[k1][k2]=bad[k2][k1]=1;
		}
		memset(vis, 0, sizeof(vis));
		dfs(visitors[i][1]);
		for (int j=0; j<4; ++j)
			if (vis[j])
				ans[visitors[i][2]]+=(char)('1'+j);
	}
	for (int i=0; i<m; ++i)
		cout << ans[i] << "\n";
	return 0;
}

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