Submission #698037

#	Time	Username	Problem	Language	Result	Execution time	Memory
698037		acceptify	Park (BOI16_park)	C++17	100 / 100	322 ms	55424 KiB

park

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

typedef long long ll;

const ll mxn = 2015;
const ll mxm = 1e5 + 5;
const ll LEFT = 2001, RIGHT = 2002, TOP = 2003, BOTTOM = 2004;

struct Circle {
	ll x, y, r;
} cir[mxn];

ll sqr(ll x) { return x * x; }
double dist(Circle a, Circle b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)) - a.r - b.r; }

struct Query {
	ll id, r, st;
	const bool operator < (const Query& rhs) { return r < rhs.r; }
} qry[mxm];

struct Edge {
	ll x, y;
    double w;
	const bool operator < (const Edge& rhs) { return w < rhs.w; }
};

ll n, m, w, h, dsu[mxn], ans[mxm][5];
vector<Edge> edges;

ll root(ll x) { return dsu[x] == x ? x : dsu[x] = root(dsu[x]); }
void join(ll x, ll y) {
	x = root(x), y = root(y);
	if (x != y) dsu[x] = y;
}

bool path(ll x, ll y) {
	if (x == y) return true;
	if ((x == 1 || y == 1) && root(LEFT) == root(BOTTOM)) return false;
	if ((x == 2 || y == 2) && root(RIGHT) == root(BOTTOM)) return false;
	if ((x == 3 || y == 3) && root(RIGHT) == root(TOP)) return false;
	if ((x == 4 || y == 4) && root(LEFT) == root(TOP)) return false;
	if (root(TOP) == root(BOTTOM)) {
		if ((x == 1 || x == 4) && (y == 2 || y == 3)) return false;
		if ((x == 2 || x == 3) && (y == 1 || y == 4)) return false;
	}
	if (root(LEFT) == root(RIGHT)) {
		if ((x == 1 || x == 2) && (y == 3 || y == 4)) return false;
		if ((x == 3 || x == 4) && (y == 1 || y == 2)) return false;
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; i++) cin >> cir[i].x >> cir[i].y >> cir[i].r;
	for (int i = 1; i <= m; i++) {
		cin >> qry[i].r >> qry[i].st;
		qry[i].id = i;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) edges.push_back({i, j, dist(cir[i], cir[j])});
		edges.push_back({i, LEFT, (double)cir[i].x - cir[i].r});
		edges.push_back({i, BOTTOM, (double)cir[i].y - cir[i].r});
		edges.push_back({i, RIGHT, (double)w - cir[i].x - cir[i].r});
		edges.push_back({i, TOP, (double)h - cir[i].y - cir[i].r});
	}
	for(int i = 1; i <= 2004; i++) dsu[i] = i;
	sort(qry + 1, qry + m + 1);
	sort(edges.begin(), edges.end());
	for (int i = 1, ptr = 0; i <= m; i++) {
		while (ptr < edges.size() && qry[i].r * 2 > edges[ptr].w) {
			join(edges[ptr].x, edges[ptr].y);
			ptr++;
		}
		for (int j = 1; j <= 4; j++) ans[qry[i].id][j] = path(qry[i].st, j);
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= 4; j++) {
			if (ans[i][j]) cout << j;
		}
		cout << "\n";
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:73:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   while (ptr < edges.size() && qry[i].r * 2 > edges[ptr].w) {
      |          ~~~~^~~~~~~~~~~~~~

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