제출 #699636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699636		nayhz	Park (BOI16_park)	C++17	100 / 100	1016 ms	90596 KiB

park

// 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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42