oj.uz

Submission #1096664

# Submission time Handle Problem Language Result Execution time Memory
1096664 2024-10-05T00:25:17 Z KickingKun Park (BOI16_park) C++14
100 / 100
 203 ms 28552 KB 
// 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;
	ll 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 = 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

park.cpp: In function 'int main()':
park.cpp:118:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |  for (auto [r, e, id]: que) {
      |            ^
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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 25284 KB Output is correct
2 Correct 178 ms 25288 KB Output is correct
3 Correct 173 ms 25272 KB Output is correct
4 Correct 173 ms 25284 KB Output is correct
5 Correct 174 ms 25300 KB Output is correct
6 Correct 170 ms 25288 KB Output is correct
7 Correct 157 ms 25288 KB Output is correct
8 Correct 159 ms 25280 KB Output is correct
9 Correct 1 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 35 ms 3732 KB Output is correct
2 Correct 28 ms 3788 KB Output is correct
3 Correct 27 ms 3788 KB Output is correct
4 Correct 28 ms 3800 KB Output is correct
5 Correct 28 ms 3788 KB Output is correct
6 Correct 30 ms 3784 KB Output is correct
7 Correct 25 ms 3536 KB Output is correct
8 Correct 24 ms 3496 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 25284 KB Output is correct
2 Correct 178 ms 25288 KB Output is correct
3 Correct 173 ms 25272 KB Output is correct
4 Correct 173 ms 25284 KB Output is correct
5 Correct 174 ms 25300 KB Output is correct
6 Correct 170 ms 25288 KB Output is correct
7 Correct 157 ms 25288 KB Output is correct
8 Correct 159 ms 25280 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 35 ms 3732 KB Output is correct
12 Correct 28 ms 3788 KB Output is correct
13 Correct 27 ms 3788 KB Output is correct
14 Correct 28 ms 3800 KB Output is correct
15 Correct 28 ms 3788 KB Output is correct
16 Correct 30 ms 3784 KB Output is correct
17 Correct 25 ms 3536 KB Output is correct
18 Correct 24 ms 3496 KB Output is correct
19 Correct 203 ms 28532 KB Output is correct
20 Correct 198 ms 28548 KB Output is correct
21 Correct 201 ms 28552 KB Output is correct
22 Correct 203 ms 28532 KB Output is correct
23 Correct 203 ms 28516 KB Output is correct
24 Correct 189 ms 28552 KB Output is correct