oj.uz

Submission #698037

# Submission time Handle Problem Language Result Execution time Memory
698037 2023-02-12T05:27:28 Z acceptify Park (BOI16_park) C++17
100 / 100
 322 ms 55424 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 49844 KB Output is correct
2 Correct 268 ms 49752 KB Output is correct
3 Correct 270 ms 49840 KB Output is correct
4 Correct 273 ms 49848 KB Output is correct
5 Correct 273 ms 49820 KB Output is correct
6 Correct 281 ms 49864 KB Output is correct
7 Correct 252 ms 49808 KB Output is correct
8 Correct 255 ms 49824 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8548 KB Output is correct
2 Correct 44 ms 8508 KB Output is correct
3 Correct 44 ms 8568 KB Output is correct
4 Correct 43 ms 8600 KB Output is correct
5 Correct 44 ms 8584 KB Output is correct
6 Correct 62 ms 8648 KB Output is correct
7 Correct 46 ms 8008 KB Output is correct
8 Correct 41 ms 8012 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 49844 KB Output is correct
2 Correct 268 ms 49752 KB Output is correct
3 Correct 270 ms 49840 KB Output is correct
4 Correct 273 ms 49848 KB Output is correct
5 Correct 273 ms 49820 KB Output is correct
6 Correct 281 ms 49864 KB Output is correct
7 Correct 252 ms 49808 KB Output is correct
8 Correct 255 ms 49824 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 55 ms 8548 KB Output is correct
12 Correct 44 ms 8508 KB Output is correct
13 Correct 44 ms 8568 KB Output is correct
14 Correct 43 ms 8600 KB Output is correct
15 Correct 44 ms 8584 KB Output is correct
16 Correct 62 ms 8648 KB Output is correct
17 Correct 46 ms 8008 KB Output is correct
18 Correct 41 ms 8012 KB Output is correct
19 Correct 322 ms 55244 KB Output is correct
20 Correct 306 ms 55176 KB Output is correct
21 Correct 319 ms 55424 KB Output is correct
22 Correct 311 ms 55232 KB Output is correct
23 Correct 311 ms 55260 KB Output is correct
24 Correct 312 ms 55384 KB Output is correct