oj.uz

Submission #753502

# Submission time Handle Problem Language Result Execution time Memory
753502 2023-06-05T11:44:14 Z MetalPower Park (BOI16_park) C++14
0 / 100
 540 ms 28364 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 + 10;
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;
	}
} 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;
}

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 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(; edges[j].fi < q.fi && j < sz; j++) D.Join(edges[j].se.fi, edges[j].se.se);

		for(int i = 1; i <= 4; i++){
			if(q.se.fi == i) ans[q.se.se] += (char)(i + '0');
			else{
				bool st = D.f(N + q.se.fi) != D.f(N + q.se.fi % 4 + 1);
				bool fn = D.f(N + i) != D.f(N + i % 4 + 1);
				if(st && fn) 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:45:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid = lf + rg >> 1;
      |             ~~~^~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 28264 KB Output is correct
2 Correct 521 ms 28200 KB Output is correct
3 Correct 510 ms 28364 KB Output is correct
4 Correct 531 ms 28288 KB Output is correct
5 Correct 528 ms 28192 KB Output is correct
6 Correct 540 ms 28188 KB Output is correct
7 Incorrect 486 ms 28180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5324 KB Output is correct
2 Correct 43 ms 5312 KB Output is correct
3 Incorrect 44 ms 5364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 28264 KB Output is correct
2 Correct 521 ms 28200 KB Output is correct
3 Correct 510 ms 28364 KB Output is correct
4 Correct 531 ms 28288 KB Output is correct
5 Correct 528 ms 28192 KB Output is correct
6 Correct 540 ms 28188 KB Output is correct
7 Incorrect 486 ms 28180 KB Output isn't correct
8 Halted 0 ms 0 KB -