oj.uz

Submission #753505

# Submission time Handle Problem Language Result Execution time Memory
753505 2023-06-05T12:07:16 Z MetalPower Park (BOI16_park) C++14
100 / 100
 592 ms 31136 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pli pair<int, pii>
#define fi first
#define se second

const int MX = 2e3 + 50;
const int MN = 1e5 + 10;

int N, M, W, H, x[MX], y[MX], r[MX];
vector<pli> edges; // weight, u, v
vector<pli> queries;

string ans[MN];

struct dsu{
	int p[MX];

	void init(){
		for(int i = 0; i < MX; i++) p[i] = i;
	}

	int f(int x){
		if(p[x] == x) return x;
		else return p[x] = f(p[x]);
	}

	void Join(int u, int v){
		int fu = f(u), fv = f(v);
		if(fu == fv) return;
		p[fu] = fv;
	}

	bool con(int u, int v){
		return f(u) == f(v);
	}
} D;

int diff(int a, int b){
	return (a > b ? a - b : b - a);
}

int bin_sqrt(ll x){
	int lf = 0, rg = 1e9, memo = -1;
	while(lf <= rg){
		int mid = lf + rg >> 1;
		if(1ll * mid * mid <= x) memo = mid, lf = mid + 1;
		else rg = mid - 1;
	}
	return memo;
}

bool check(int a, int b){ // check if entrance a and b is connected or not
	if(a == b) return true;
	if(a > b) swap(a, b);

	bool ex = !D.con(N + a, N + a % 4 + 1) && !D.con(N + b, N + b % 4 + 1);

	if((a == 1 && b == 2) || (a == 3 && b == 4)) return ex && !D.con(N + 2, N + 4);
	else if((a == 1 && b == 3) || (a == 2 && b == 4)) return ex && !D.con(N + 2, N + 4) && !D.con(N + 1, N + 3);
	else if((a == 1 && b == 4) || (a == 2 && b == 3)) return ex && !D.con(N + 1, N + 3);
	else return ex;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M >> W >> H;

	D.init();

	for(int i = 1; i <= N; i++){
		cin >> x[i] >> y[i] >> r[i];
		edges.push_back({(x[i] - r[i]) / 2, {N + 1, i}}); // maximum integer radius that can pass, aka is disconnected
		edges.push_back({(y[i] - r[i]) / 2, {N + 2, i}}); 
		edges.push_back({(W - x[i] - r[i]) / 2, {N + 3, i}});
		edges.push_back({(H - y[i] - r[i]) / 2, {N + 4, i}});
	}

	for(int i = 1; i <= N; i++){
		for(int j = i + 1; j <= N; j++){
			int dx = diff(x[i], x[j]), dy = diff(y[i], y[j]);
			int dist = (int) bin_sqrt(1ll * dx * dx + 1ll * dy * dy) - r[i] - r[j];
			edges.push_back({dist / 2, {i, j}});
		}
	}

	for(int i = 1; i <= M; i++){
		int rd, st; cin >> rd >> st;
		queries.push_back({rd, {st, i}});
	}

	int sz = edges.size();
	sort(edges.begin(), edges.end());
	sort(queries.begin(), queries.end());

	int j = 0;
	for(pli q : queries){
		for(; j < sz && edges[j].fi < q.fi; j++) D.Join(edges[j].se.fi, edges[j].se.se);

		for(int i = 1; i <= 4; i++){
			if(check(q.se.fi, i)) ans[q.se.se] += (char)(i + '0');
		}
	}

	for(int i = 1; i <= M; i++) cout << ans[i] << '\n';
}

Compilation message

park.cpp: In function 'int bin_sqrt(long long int)':
park.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid = lf + rg >> 1;
      |             ~~~^~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 28188 KB Output is correct
2 Correct 533 ms 28148 KB Output is correct
3 Correct 529 ms 28216 KB Output is correct
4 Correct 553 ms 28232 KB Output is correct
5 Correct 551 ms 28248 KB Output is correct
6 Correct 539 ms 28184 KB Output is correct
7 Correct 493 ms 28212 KB Output is correct
8 Correct 479 ms 28172 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3464 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5332 KB Output is correct
2 Correct 46 ms 5340 KB Output is correct
3 Correct 51 ms 5388 KB Output is correct
4 Correct 49 ms 6364 KB Output is correct
5 Correct 47 ms 6344 KB Output is correct
6 Correct 47 ms 6448 KB Output is correct
7 Correct 40 ms 6172 KB Output is correct
8 Correct 42 ms 6220 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 28188 KB Output is correct
2 Correct 533 ms 28148 KB Output is correct
3 Correct 529 ms 28216 KB Output is correct
4 Correct 553 ms 28232 KB Output is correct
5 Correct 551 ms 28248 KB Output is correct
6 Correct 539 ms 28184 KB Output is correct
7 Correct 493 ms 28212 KB Output is correct
8 Correct 479 ms 28172 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3464 KB Output is correct
11 Correct 44 ms 5332 KB Output is correct
12 Correct 46 ms 5340 KB Output is correct
13 Correct 51 ms 5388 KB Output is correct
14 Correct 49 ms 6364 KB Output is correct
15 Correct 47 ms 6344 KB Output is correct
16 Correct 47 ms 6448 KB Output is correct
17 Correct 40 ms 6172 KB Output is correct
18 Correct 42 ms 6220 KB Output is correct
19 Correct 579 ms 31060 KB Output is correct
20 Correct 574 ms 31116 KB Output is correct
21 Correct 575 ms 31116 KB Output is correct
22 Correct 579 ms 31064 KB Output is correct
23 Correct 592 ms 31104 KB Output is correct
24 Correct 531 ms 31136 KB Output is correct