oj.uz

Submission #634166

# Submission time Handle Problem Language Result Execution time Memory
634166 2022-08-23T23:44:09 Z SharpEdged Park (BOI16_park) C++17
100 / 100
 311 ms 55904 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)x.size())

typedef long long ll;

using namespace std;

// the below program uses squares of distances for that neat no-"double" usage code

vector<int> par, rnk;
vector<vector<int>> con;
vector<ll> x, y, r;

vector<vector<int>> adj(4, vector<int>(4));

void updateAdj(int a){
	for (int i = 0; i < 4; i++){
		if (!con[a][i]) continue;
		for (int j = 0; j < 4; j++){
			if (!con[a][j]) continue;
			adj[i][j] = 1;
		}
	}
}

int findP(int a){
	return par[a] = (par[a] == a) ? a : findP(par[a]);
}

void unite(int a, int b){
	a = findP(a); b = findP(b);
	if (a == b) return;
	if (rnk[a] > rnk[b]) swap(a, b);
	if (rnk[a] == rnk[b]) rnk[b]++;
	par[a] = b;
	for (int i = 0; i < 4; i++){ con[b][i] |= con[a][i]; }
	updateAdj(b);
}

void connect(int a, int wall){
	a = findP(a);
	con[a][wall] = 1;
	updateAdj(a);
}

struct Link {
	int a, b, wall;
	ll dist;
	Link(int _a, int _b, ll _dist, int _wall) {
		a = _a; b = _b; dist = _dist; wall = _wall;
	}
	bool operator<(const Link& other) const {
		return dist < other.dist;
	}
	bool Join(double len){
		if (len <= dist) return 0;
		
		if (wall) connect(a, b);
		else unite(a, b);
		return 1;
	}
};

struct Query{
	ll r; int e, id;
	Query(ll _r, int _e, int _id) {
		r = _r; e = _e; id = _id;
	}
	bool operator<(const Query& other) const {
		return r < other.r;
	}
};

void printAdj(){
	cout << "??\n\n";
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++){
			cout << adj[i][j] << " ";
		}
		cout << "\n";
	}
}

string GetAns(int e){
	int prev = (e + 3) % 4;
	int mid = (e + 2) % 4;
	int nxt = (e + 1) % 4;
	vector<int> ok = { e+1 };
	
	//printAdj();
	
	// e -> next
	if (!adj[nxt][e] && !adj[nxt][mid] && !adj[nxt][prev]) ok.pb(nxt+1);
	// e -> middle
	if (!adj[e][nxt] && !adj[mid][prev] && !adj[e][mid] && !adj[nxt][prev]) ok.pb(mid+1);
	// e -> previous
	if (!adj[e][prev] && !adj[e][mid] && !adj[e][nxt]) ok.pb(prev+1);
	
	string res = "";
	sort(all(ok));
	for (int i = 0; i < sz(ok); i++) res += to_string(ok[i]);
	return res;
}

char nl = '\n';

int main() {
	int n, m;
	ll w, h;
	cin >> n >> m >> w >> h;
	x.resize(n); y.resize(n); r.resize(n);
	vector<Link> links;
	for (int i = 0; i < n; i++){
		par.pb(i); rnk.pb(0); con.pb(vector<int>(4));
		cin >> x[i] >> y[i] >> r[i];
		links.eb(i, 0, x[i] - r[i], 1);
		links.eb(i, 1, y[i] - r[i], 1);
		links.eb(i, 2, w - x[i] - r[i], 1);
		links.eb(i, 3, h - y[i] - r[i], 1);
	}
	for (int i = 0; i < n; i++){
		for (int j = i+1; j < n; j++){
			ll dx = x[i] - x[j];
			ll dy = y[i] - y[j];
			links.eb(i, j, sqrt(dx * dx + dy * dy) - r[i] - r[j], 0);
		}
	}
	vector<string> ans(m);
	vector<Query> qrys;
	for (int i = 0; i < m; i++){
		ll rad; int e;
		cin >> rad >> e;
		qrys.eb(rad, e-1, i);
	}

	sort(all(qrys));
	sort(all(links));

	int curLink = 0;

	for (int i = 0; i < m; i++) {
		ll rad = qrys[i].r; int e = qrys[i].e, id = qrys[i].id;

		while (curLink < sz(links) && links[curLink].Join(2*rad)) {
			curLink++;
		}
		
		ans[id] = GetAns(e);
	}

	for (int i = 0; i < m; i++) cout << ans[i] << nl;
	return 0;
}

/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
 */

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 49816 KB Output is correct
2 Correct 237 ms 49952 KB Output is correct
3 Correct 230 ms 49848 KB Output is correct
4 Correct 229 ms 49884 KB Output is correct
5 Correct 230 ms 49880 KB Output is correct
6 Correct 229 ms 49836 KB Output is correct
7 Correct 228 ms 49860 KB Output is correct
8 Correct 215 ms 49924 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 6380 KB Output is correct
2 Correct 79 ms 7380 KB Output is correct
3 Correct 79 ms 7292 KB Output is correct
4 Correct 81 ms 7364 KB Output is correct
5 Correct 80 ms 7372 KB Output is correct
6 Correct 81 ms 7388 KB Output is correct
7 Correct 82 ms 6592 KB Output is correct
8 Correct 77 ms 6552 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 49816 KB Output is correct
2 Correct 237 ms 49952 KB Output is correct
3 Correct 230 ms 49848 KB Output is correct
4 Correct 229 ms 49884 KB Output is correct
5 Correct 230 ms 49880 KB Output is correct
6 Correct 229 ms 49836 KB Output is correct
7 Correct 228 ms 49860 KB Output is correct
8 Correct 215 ms 49924 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 81 ms 6380 KB Output is correct
12 Correct 79 ms 7380 KB Output is correct
13 Correct 79 ms 7292 KB Output is correct
14 Correct 81 ms 7364 KB Output is correct
15 Correct 80 ms 7372 KB Output is correct
16 Correct 81 ms 7388 KB Output is correct
17 Correct 82 ms 6592 KB Output is correct
18 Correct 77 ms 6552 KB Output is correct
19 Correct 306 ms 55904 KB Output is correct
20 Correct 309 ms 55652 KB Output is correct
21 Correct 311 ms 55684 KB Output is correct
22 Correct 300 ms 55644 KB Output is correct
23 Correct 302 ms 55652 KB Output is correct
24 Correct 303 ms 55800 KB Output is correct