Submission #389805

#	Time	Username	Problem	Language	Result	Execution time	Memory
389805		Cantfindme	Park (BOI16_park)	C++17	100 / 100	1325 ms	139232 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

#define ld long double

typedef pair<ld, pi> pii;
 
const int maxn = 2050;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7; 

int n,Q;
int W, H;

int parent[maxn];
int findp(int x){ 
	if (parent[x] == x) return x;
	return parent[x] = findp(parent[x]);
}

//n -> left wall, n+1, right wall, n+2, up wall, n+3 down wall
//1 = bottom-left, 2 = bottom-right, 3 = top-right, 4 = top-left

map <pi,int> mp;
int isblock[5];

vector <pii> v;
vector <pii> queries;
string rans[100010];

ld calc(pi a, pi b) {
	return sqrt((ld)abs(a.f - b.f) * abs(a.f - b.f) + abs(a.s - b.s) * abs(a.s-b.s));
}

void upblock(int a, int b) {
	if (a > b) swap(a,b);
	if (a == n and b == n+1) { //block left to right
		mp[pi(1,4)] = mp[pi(4,1)] = mp[pi(3,2)] = mp[pi(2,3)] = 1;
		mp[pi(1,3)] = mp[pi(3,1)] = mp[pi(2,4)] = mp[pi(4,2)] = 1;
	}
	
	if (a == n+2 and b == n+3) { //block up to down
		mp[pi(4,3)] = mp[pi(3,4)] = mp[pi(1,2)] = mp[pi(2,1)] = 1;
		mp[pi(4,2)] = mp[pi(2,4)] = mp[pi(1,3)] = mp[pi(3,1)] = 1;
	}
	
	if (a == n and b == n+3) { //block 1
		isblock[1] = 1;
	}
	
	if (a == n+1 and b == n+3) { //block 2
		isblock[2] = 1;
	}
	
	if (a == n+1 and b == n+2) { //block 3
		isblock[3] = 1;
	}
	
	if (a == n and b == n+2) { //block 4
		isblock[4] = 1;
	}
	
}

void check() {
	for (int i = n; i <= n+3; i++) {
		for (int j =i+1;j<=n+3;j++) {
			if (findp(i) == findp(j)) upblock(i,j);
		}
	}
}

void checkans(pii qq) {
	int e = qq.s.f;
	int indx = qq.s.s;
	
	vector <int> ans = {e};

	if (!isblock[e]) {
		for (int j = 1; j <=4;j++) {			
			if (j == e) continue;
			if (isblock[j]) continue;
			if (mp[pi(j,e)]) continue;
			ans.push_back(j);
		}
	}
	
	sort(all(ans));
	rans[indx] = "";
	for (auto i: ans) rans[indx] += to_string(i); 
}

int32_t main() {
	FAST
	cin >> n >> Q;
	cin >> W >> H;
	
	for (int i =0;i<n+4;i++) parent[i] = i;
	
	for (int i =0;i<n;i++) {
		int x,y,r; cin >> x >> y >> r;
		v.push_back(pii(r,pi(x,y)));
	}
	
	for (int i =0;i<Q;i++) {
		int r, e; cin >> r >> e;
		queries.push_back(pii(r,pi(e,i)));
	}
	
	vector <pii> edges;
	
	for (int i =0;i<n;i++) {
		for (int j =0;j<n;j++) {
			if (i == j) continue;
			ld totald = calc(v[i].s, v[j].s);
			edges.push_back(pii(totald - v[i].f - v[j].f, pi(i,j)));
		}
		
		edges.push_back(pii(v[i].s.f - v[i].f, pi(i,n))); //left wall
		edges.push_back(pii(W - v[i].s.f - v[i].f,pi(i,n+1))); //right wall
		edges.push_back(pii(v[i].s.s - v[i].f, pi(i,n+3))); //down wall
		edges.push_back(pii(H - v[i].s.s - v[i].f, pi(i,n+2))); //up wall
	}
	
	sort(all(edges));
	sort(all(queries));
	
	int co = 0;
	for (auto [d, cur] : edges) {
		while (co < Q and queries[co].f*2 <= d) {
			checkans(queries[co]);
			co++;
		}
		
		auto [a,b] = cur;
		if (findp(a) == findp(b)) continue;
		parent[findp(a)] = findp(b);
	
		check();
	}
	
	while (co < Q) {
		checkans(queries[co]);
		co++;
	}
	
	for (int i =0;i<Q;i++) {
		cout << rans[i] << "\n";
	}
}

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