oj.uz

Submission #1003678

# Submission time Handle Problem Language Result Execution time Memory
1003678 2024-06-20T15:13:33 Z sano Park (BOI16_park) C++14
100 / 100
 556 ms 107296 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short ll
#define pii pair<ll, ll>
#define NEK 1000000000
#define mod1 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8

using namespace std;

vec<ll> o;

double dist(pii a, pii b) {
	return sqrt(abs(a.ff - b.ff) * abs(a.ff - b.ff) + abs(a.ss - b.ss) * abs(a.ss - b.ss));
}

struct strom {
	ll x, y, r;
};

struct hrana {
	ll x, y;
	double w;
	bool operator<(const hrana& other) const {
		return w > other.w;
	}
};

struct clovek {
	ll r, e, ind;
	bool operator<(const clovek& other) const {
		return r < other.r;
	}
};

ll otec(ll x) {
	if (o[x] < 0) return x;
	o[x] = otec(o[x]);
	return o[x];
}

bool spoj(ll a, ll b) {
	if (otec(a) == otec(b)) return true;
	o[otec(b)] = otec(a);
	return true;
}

bool je(ll a, ll b) {
	return otec(a) == otec(b);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll n, m, w, h;
	cin >> n >> m >> w >> h;
	vec<strom> s;
	For(i, n) {
		ll x, y, r;
		cin >> x >> y >> r;
		s.push_back({ x, y, r });
	}
	vec<hrana> p;
	For(i, n) {
		For(j, n) {
			if (i == j) continue;
			p.push_back({ i, j, { double((dist({s[i].x, s[i].y}, {s[j].x, s[j].y}) - s[i].r - s[j].r) / 2) } });
		}
	}
	For(i, n) {
		p.push_back({ i, n, double((s[i].y - s[i].r) / 2) });
		p.push_back({ i, n + 1, double((w - s[i].x - s[i].r) / 2) });
		p.push_back({ i, n + 2, double((h - s[i].y - s[i].r) / 2) });
		p.push_back({ i, n + 3, double((s[i].x - s[i].r) / 2) });
	}
	o.resize(n + 4, -1);
	sort(p.begin(), p.end());
	vec<clovek> l;
	vec<vec<bool>> odp(m, vec<bool>(4, false));
	For(i, m) {
		ll r, e;
		cin >> r >> e;
		l.push_back({ r, e, i });;
	}
	sort(l.begin(), l.end());
	For(i, m) {
		ll r = l[i].r; ll e = l[i].e;
		while (!p.empty()) {
			if (p.back().w >= r) break;
			spoj(p.back().x, p.back().y);
			p.pop_back();
		}
		ll v1 = e - 1;
		ll v2 = e;
		ll v3 = e + 1;
		ll v4 = e + 2;
		if (v2 > 3) v2 -= 4;
		if (v3 > 3) v3 -= 4;
		if (v4 > 3) v4 -= 4;
		v1 += n; v2 += n; v3 += n; v4 += n;
		odp[l[i].ind][e - 1] = true;
		if (!je(v1, v2) && !je(v1, v3) && !je(v1, v4)) {
			ll qwe = (2 + e - 1);
			if (qwe > 4) qwe -= 4;
			odp[l[i].ind][qwe - 1] = true;;
		}
		if (!je(v2, v3) && !je(v2, v4) && !je(v1, v3) && !je(v1, v4)) {
			ll qwe = (3 + e - 1);
			if (qwe > 4) qwe -= 4;
			odp[l[i].ind][qwe - 1] = true;
		}
		if (!je(v4, v1) && !je(v4, v2) && !je(v4, v3)) {
			ll qwe = (4 + e - 1);
			if (qwe > 4) qwe -= 4;
			odp[l[i].ind][qwe - 1] = true;
		}
	}
	For(i, m) {
		For(j, odp[i].size()) {
			if (!odp[i][j]) continue;
			cout << j + 1;
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 99000 KB Output is correct
2 Correct 462 ms 99068 KB Output is correct
3 Correct 463 ms 99100 KB Output is correct
4 Correct 504 ms 99184 KB Output is correct
5 Correct 516 ms 99196 KB Output is correct
6 Correct 517 ms 98996 KB Output is correct
7 Correct 466 ms 99000 KB Output is correct
8 Correct 486 ms 98996 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11684 KB Output is correct
2 Correct 51 ms 11604 KB Output is correct
3 Correct 48 ms 11608 KB Output is correct
4 Correct 42 ms 11608 KB Output is correct
5 Correct 43 ms 11604 KB Output is correct
6 Correct 45 ms 11640 KB Output is correct
7 Correct 36 ms 11728 KB Output is correct
8 Correct 38 ms 10704 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 99000 KB Output is correct
2 Correct 462 ms 99068 KB Output is correct
3 Correct 463 ms 99100 KB Output is correct
4 Correct 504 ms 99184 KB Output is correct
5 Correct 516 ms 99196 KB Output is correct
6 Correct 517 ms 98996 KB Output is correct
7 Correct 466 ms 99000 KB Output is correct
8 Correct 486 ms 98996 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 50 ms 11684 KB Output is correct
12 Correct 51 ms 11604 KB Output is correct
13 Correct 48 ms 11608 KB Output is correct
14 Correct 42 ms 11608 KB Output is correct
15 Correct 43 ms 11604 KB Output is correct
16 Correct 45 ms 11640 KB Output is correct
17 Correct 36 ms 11728 KB Output is correct
18 Correct 38 ms 10704 KB Output is correct
19 Correct 534 ms 107296 KB Output is correct
20 Correct 547 ms 107296 KB Output is correct
21 Correct 553 ms 107260 KB Output is correct
22 Correct 541 ms 107292 KB Output is correct
23 Correct 556 ms 107148 KB Output is correct
24 Correct 497 ms 107292 KB Output is correct