Submission #1096477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096477		KickingKun	Park (BOI16_park)	C++17	0 / 100	188 ms	25288 KiB

park

// PHK

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""

#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))
#define lowBit(k) (31 - __builtin_clz(k & -k))

template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}

const int N = 2e3 + 10, lim = 1e5 + 2, mod = 1e9 + 7;
const ll INF = 1e18;

// BOI 2016

struct Edge {
	int u, v, d;
	Edge () {}
	Edge (int _u, int _v, int _d) {
		u = _u; v = _v; d = _d;
	}
	bool operator < (const Edge &other) {
		return d < other.d;
	}
};
struct Circle {
	int x, y, r;
	double dis(const Circle &b) {
		return sqrt((1ll * (x - b.x) * (x - b.x)) + (1ll * (y - b.y) * (y - b.y)));
	}
} cir[N];
struct Query {
	int r, e, id;
	Query () {}
	Query (int _r, int _e, int _id) {
		r = _r; e = _e; id = _id;
	}
	bool operator < (const Query &other) {
		return r < other.r;
	}
};

struct DSU {
	vector <int> par, sz;
	DSU (int n) {
		par.assign(n + 1, 0); sz.assign(n + 1, 1);
	}
	int find_set(int u) {
		return par[u] ? par[u] = find_set(par[u]) : u;
	}
	bool unite(int u, int v) {
		u = find_set(u); v = find_set(v);
		if (u == v) return false;
		if (sz[u] < sz[v]) swap(u, v);
		sz[par[v] = u] += sz[v];
		return true;
	}
	bool same_set(int u, int v) {
		return find_set(u) == find_set(v);
	}
};

int n, m, w, h;
vector <Edge> edge;
vector <Query> que;
bool reach[lim][5], canGo[5][5];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    if (fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    
    // n + 1, n + 2, n + 3, n + 4: top, left, bottom, right border
    
	cin >> n >> m >> w >> h;
	for (int i = 1; i <= n; i++) {
		cin >> cir[i].x >> cir[i].y >> cir[i].r;
		for (int j = 1; j < i; j++) {
			ll dist = ceil(cir[i].dis(cir[j])) - cir[i].r - cir[j].r;
			edge.emb(i, j, dist);
		}
		edge.emb(n + 1, i, h - cir[i].y - cir[i].r);
		edge.emb(n + 2, i, cir[i].x - cir[i].r);
		edge.emb(n + 3, i, cir[i].y - cir[i].r);
		edge.emb(n + 4, i, w - cir[i].x - cir[i].r);
	}
	sort (all(edge));
	
	for (int i = 0; i < m; i++) {
		int r, e; cin >> r >> e;
		que.emb(r, e, i);
	}
	sort (all(que));
	
	int p = -1; DSU dsu(n + 4);
	for (auto [r, e, id]: que) {
		while (p + 1 < edge.size() && edge[p + 1].d <= r * 2) {
			++p; dsu.unite(edge[p].u, edge[p].v);
//			cout << edge[p].u << ' ' << edge[p].v << '\n';
		}
		
		// 4 3
		// 1 2
		
		memset(canGo, true, sizeof canGo);
		if (dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 2, n + 3) || dsu.same_set(n + 3, n + 4)) 
			canGo[1][2] = false;
		if (dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 2, n + 3) || dsu.same_set(n + 1, n + 4))
			canGo[1][3] = false;
		if (dsu.same_set(n + 1, n + 2) || dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 2, n + 3))
			canGo[1][4] = false;
		if (dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 1, n + 4) || dsu.same_set(n + 3, n + 4))
			canGo[2][3] = false;
		if (dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 1, n + 2) || dsu.same_set(n + 3, n + 4))
			canGo[2][4] = false;
		if (dsu.same_set(n + 1, n + 2) || dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 1, n + 4))
			canGo[3][4] = false;
		
		for (int i = 1; i <= 4; i++)
			reach[id][i] = canGo[min(i, e)][max(i, e)];
	}
	
	for (int i = 0; i < m; i++) {
		string res;
		for (int x = 1; x <= 4; x++)
			if (reach[i][x]) res += char(x + 48);
		cout << res << '\n';
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   while (p + 1 < edge.size() && edge[p + 1].d <= r * 2) {
      |          ~~~~~~^~~~~~~~~~~~~
park.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(Task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(Task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42