Submission #31916

#	Time	Username	Problem	Language	Result	Execution time	Memory
31916		UncleGrandpa925	Park (BOI16_park)	C++14	27 / 100	1106 ms	80880 KiB

park

/*input
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 103005
#define bit(x,y) ((x>>y)&1LL)
#define show(x) cout << (#x) << ": " << x << endl;
#define ii pair<int,int>
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}
struct Circle {
	int x, y, r;
	Circle(int _x, int _y, int _r): x(_x), y(_y), r(_r) {};
};

struct Visitor {
	int r, gate, id;
	Visitor(int _r, int _gate, int _id): r(_r), gate(_gate), id(_id) {};
};

struct Event {
	int r, u, v;
	Event(int _r, int _u, int _v): r(_r), u(_u), v(_v) {};
};

struct dsu {
	int par[N];
	dsu() {
		for (int i = 1; i <= N - 5; i++) par[i] = i;
	}
	int find(int x) {
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	void uni(int x, int y) {
		x = find(x); y = find(y);
		if (x != y) par[x] = y;
	}
} d;

bool operator < (Event x, Event y) {
	return x.r < y.r;
}

bool operator < (Visitor x, Visitor y) {
	return x.r < y.r;
}

int n, m;
int W, H;
vector<Circle> circle;
vector<Visitor> visitor;
vector<Event> event;
int ans[N][5];
// m, m+1, m+2, m+3 lan luot la goc duoi, phai, tren, trai cua hinh chu nhat
bool canPass(int lim, int u, int v) {
	if (u >= n) {
		if (v >= n) return 1;
		if (u == n) return circle[v].y - circle[v].r >= 2 * lim;
		if (u == n + 1) return W - (circle[v].x + circle[v].r) >= 2 * lim;
		if (u == n + 2) return H - (circle[v].y + circle[v].r) >= 2 * lim;
		if (u == n + 3) return circle[v].x - circle[v].r >= 2 * lim;
		return 0;
	}
	if (v >= n) return canPass(lim, v, u);
	int dx = circle[u].x - circle[v].x;
	int dy = circle[u].y - circle[v].y;
	int dis = dx * dx + dy * dy;
	int mdis = circle[u].r + circle[v].r + 2 * lim;
	mdis *= mdis;
	return dis >= mdis;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	cin >> W >> H;
	for (int i = 1; i <= n; i++) {
		int x, y, z; cin >> x >> y >> z;
		circle.push_back(Circle(x, y, z));
	}
	for (int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		visitor.push_back(Visitor(x, y, i));
	}
	sort(visitor.begin(), visitor.end());
	for (int i = 0; i < n + 4; i++) {
		for (int j = i + 1; j < n + 4; j++) {
			int l = 0, r = W + H;
			while (l != r) {
				int mid = (l + r + 1) / 2;
				if (canPass(mid, i, j)) l = mid;
				else r = mid - 1;
			}
			event.push_back(Event(l, i, j));
		}
	}
	sort(event.begin(), event.end());
	int it = 0;
	for (auto cur : visitor) {
		while (it < event.size() && event[it].r < cur.r) {
			d.uni(event[it].u, event[it].v);
			it++;
		}
		int gate = cur.gate - 1;
		auto con = [gate](int x, int y) {
			return d.find(n + (gate + x) % 4) == d.find(n + (gate + y) % 4);
		};
		ans[cur.id][gate] = true;
		if (!con(0, 1) && !con(0, 2) && !con(0, 3)) ans[cur.id][gate + 1] = true;
		if (!con(0, 2) && !con(0, 3) && !con(1, 2)) ans[cur.id][(gate + 2) % 4] = true;
		if (!con(0, 3) && !con(2, 3) && !con(1, 3)) ans[cur.id][(gate + 3) % 4] = true;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) if (ans[i][j]) cout << j + 1;
		cout << endl;
	}
}

Compilation message (stderr)

park.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
park.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
park.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
park.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
park.cpp: In function 'int main()':
park.cpp:147:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (it < event.size() && event[it].r < cur.r) {
             ^

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