oj.uz

Submission #753501

# Submission time Handle Problem Language Result Execution time Memory
753501 2023-06-05T11:37:31 Z MetalPower Park (BOI16_park) C++14
0 / 100
 245 ms 28312 KB 
#include <bits/stdc++.h>
using namespace std;

#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 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 = 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';
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 28252 KB Output is correct
2 Correct 221 ms 28212 KB Output is correct
3 Correct 220 ms 28220 KB Output is correct
4 Correct 229 ms 28272 KB Output is correct
5 Correct 245 ms 28212 KB Output is correct
6 Correct 245 ms 28312 KB Output is correct
7 Incorrect 209 ms 28212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6304 KB Output is correct
2 Correct 43 ms 6320 KB Output is correct
3 Incorrect 48 ms 6436 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 28252 KB Output is correct
2 Correct 221 ms 28212 KB Output is correct
3 Correct 220 ms 28220 KB Output is correct
4 Correct 229 ms 28272 KB Output is correct
5 Correct 245 ms 28212 KB Output is correct
6 Correct 245 ms 28312 KB Output is correct
7 Incorrect 209 ms 28212 KB Output isn't correct
8 Halted 0 ms 0 KB -