oj.uz

Submission #699636

# Submission time Handle Problem Language Result Execution time Memory
699636 2023-02-17T15:24:23 Z nayhz Park (BOI16_park) C++17
100 / 100
 1016 ms 90596 KB 
// source identifier task_name
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#define lck cout << "ick bmi 32.9\n"
#define cam_cs cout << "ick orz\n"
#define orz(x) cout << (x) << " orz\n"

#define pii pair<int, int>
#define pll pair<long long, long long>
#define pcc pair<char, char>
#define ll long long
#define ull unsignedge long long
#define ld long double
#define int long long

#define vi vector<int>
#define vll vector<long long>
#define vd vector<double>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long, long long>>
#define vc vector<char>
#define vsc vector<string>
#define vb vector<bool>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define yes() cout << "Yes\n"
#define no() cout << "No\n"
#define impossible() cout << "Impossible\n"

template<typename T, typename V>
inline void print (const std::pair<T, V> &x) {std::cout << x.first << ' ' << x.second << '\n';}
template<typename T>
inline void print (const T &x) {std::cout << x << '\n';}
template<typename T>
inline void print (std::vector<T> &x) {for (auto &y : x) std::cout << y << " "; std::cout << '\n';}
inline void print () {std::cout << '\n';}
template<typename... T>
inline void print(T&&... args) {((std::cout << args << " "), ...);std::cout << '\n';}
using namespace std;

const ld pi = acos(-1);
const ld eps = 1e-9;
const ll mod = 1000000007;
const ll inf = 1000000007;

clock_t T, NT;
inline double get_time() {NT = clock() - T; return (double)(NT) / CLOCKS_PER_SEC;}

void file_io (string x);

/*
>>>>>>>>>>>>>>>>>>>>>>>>>>END OF TEMPLATE HEADER<<<<<<<<<<<<<<<<<<<<<<<<
*/

template<int SZ> struct DSU {
	int parent[SZ], sz[SZ];

	void init () {
		for (int i = 0; i < SZ; i++) parent[i] = i, sz[i] = 1;
	}
	int find (int x) {
		return parent[x] == x ? x : parent[x] = find(parent[x]);
	}
	void merge (int u, int v) {
		int a = find(u), b = find(v);
		if (a == b) return;
		if (sz[a] < sz[b]) swap(a, b);
		parent[b] = a;
		sz[a] += sz[b];
	}
};

DSU<2005> dsu;

void solve (/*int &tc*/) {
	int n, m, w, h; cin >> n >> m >> w >> h;
	vector<pair<pii, int>> trees(n);
	set<pii> pts;
	vector<pair<int, pair<pii, pii>>> edge;
	map<pii, int> cc;

	auto dist = [&] (int x1, int y1, int x2, int y2) {
		return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
	};
	auto add = [&] (int x1, int y1, int x2, int y2, int r1, int r2) {
		int ndist = dist(x1, y1, x2, y2) - r1 - r2;
		edge.pb({ndist, {{x1, y1}, {x2, y2}}});
	};

	for (int i = 0; i < n; i++) {
		cin >> trees[i].fi.fi >> trees[i].fi.se >> trees[i].se;
		pts.insert({trees[i].fi.fi, trees[i].fi.se});
		cc[{0, trees[i].fi.se}] = 3;
		cc[{trees[i].fi.fi, h}] = 2;
		cc[{w, trees[i].fi.se}] = 1;
		cc[{trees[i].fi.fi, 0}] = 0;
		add(trees[i].fi.fi, trees[i].fi.se, 0, trees[i].fi.se, trees[i].se, 0);
		add(trees[i].fi.fi, trees[i].fi.se, trees[i].fi.fi, 0, trees[i].se, 0);
		add(trees[i].fi.fi, trees[i].fi.se, w, trees[i].fi.se, trees[i].se, 0);
		add(trees[i].fi.fi, trees[i].fi.se, trees[i].fi.fi, h, trees[i].se, 0);
	}

	int cnt = 4;
	for (auto &x : pts) cc[x] = cnt++;

	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) add(trees[i].fi.fi, trees[i].fi.se, trees[j].fi.fi, trees[j].fi.se, trees[i].se, trees[j].se);

	vector<pair<pii, int>> queries;
	for (int i = 0; i < m; i++) {
		int r, e; cin >> r >> e;
		e--;
		queries.pb({{(r << 1), e}, i});
	}
	sort(all(queries));
	sort(all(edge));
	dsu.init();
	int pt = 0;
	vector<vb> ok(m + 5, vb(4, true));
	for (auto e : edge) {
		while (pt < (int)queries.size() && queries[pt].fi.fi <= e.fi) {
			bool conn[4][4];
			pair<pii, int> curr = queries[pt];

			for (int i = 0; i < 4; i++) {
				conn[i][i] = true;
				for (int j = i + 1; j < 4; j++) conn[i][j] = conn[j][i] = (dsu.find(i) == dsu.find(j));
			}

			function<bool(int)> bad = [&] (int x) {
				return conn[(x - 1 < 0 ? 3 : x - 1)][x];
			};

			for (int i = 0; i < 4; i++) {
				if (curr.fi.se == i) continue;
				if (bad(curr.fi.se) || bad(i)) {
					ok[curr.se][i] = false;
					continue;
				}

				bool up = conn[0][2];
				bool side = conn[1][3];
				if (abs(curr.fi.se - i) == 2) {
					if (up || side) {
						ok[curr.se][i] = false;
						continue;
					}
				}
				else if (curr.fi.se + i == 3) {
					if (side) {
						ok[curr.se][i] = false;
						continue;
					}
				}
				else if (up) {
					ok[curr.se][i] = false;
				}
			}
			pt++;
			if (pt >= (int)queries.size()) break;
		}
		dsu.merge(cc[e.se.fi], cc[e.se.se]);
	}

	for (int i = 0; i < m; i++) {
		string ans = "";
		for (int j = 0; j < 4; j++) if (ok[i][j]) ans.pb((char)(j + '1'));
		cout << ans << '\n';
	}
}

signed main () {
	cin.tie(0)->sync_with_stdio(false);
	T = clock();
	srand(time(NULL));
	// file_io("");

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(/*i*/);
		// if (i != t) cout << '\n';
	}
	// while (true) {solve(t); t++;}
	return 0;
}

// void file_io (string x = "x") {
// 	string i = x + ".in";
// 	freopen(i.c_str(), "r", stdin);
// 	string o = x + ".out";
// 	freopen(o.c_str(), "w", stdout);
// }

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 83156 KB Output is correct
2 Correct 949 ms 83228 KB Output is correct
3 Correct 937 ms 83196 KB Output is correct
4 Correct 954 ms 83184 KB Output is correct
5 Correct 966 ms 83192 KB Output is correct
6 Correct 936 ms 83276 KB Output is correct
7 Correct 868 ms 82972 KB Output is correct
8 Correct 878 ms 82940 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11936 KB Output is correct
2 Correct 62 ms 11928 KB Output is correct
3 Correct 61 ms 11956 KB Output is correct
4 Correct 60 ms 11964 KB Output is correct
5 Correct 61 ms 12040 KB Output is correct
6 Correct 60 ms 11980 KB Output is correct
7 Correct 65 ms 11120 KB Output is correct
8 Correct 58 ms 11160 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 83156 KB Output is correct
2 Correct 949 ms 83228 KB Output is correct
3 Correct 937 ms 83196 KB Output is correct
4 Correct 954 ms 83184 KB Output is correct
5 Correct 966 ms 83192 KB Output is correct
6 Correct 936 ms 83276 KB Output is correct
7 Correct 868 ms 82972 KB Output is correct
8 Correct 878 ms 82940 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 62 ms 11936 KB Output is correct
12 Correct 62 ms 11928 KB Output is correct
13 Correct 61 ms 11956 KB Output is correct
14 Correct 60 ms 11964 KB Output is correct
15 Correct 61 ms 12040 KB Output is correct
16 Correct 60 ms 11980 KB Output is correct
17 Correct 65 ms 11120 KB Output is correct
18 Correct 58 ms 11160 KB Output is correct
19 Correct 1016 ms 90484 KB Output is correct
20 Correct 1004 ms 90356 KB Output is correct
21 Correct 997 ms 90596 KB Output is correct
22 Correct 989 ms 90436 KB Output is correct
23 Correct 1004 ms 90408 KB Output is correct
24 Correct 930 ms 90448 KB Output is correct