oj.uz

Submission #1096479

# Submission time Handle Problem Language Result Execution time Memory
1096479 2024-10-04T14:53:35 Z KickingKun Park (BOI16_park) C++17
0 / 100
 207 ms 49936 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

#define int ll

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];

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

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

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 49936 KB Output is correct
2 Correct 206 ms 49804 KB Output is correct
3 Correct 207 ms 49824 KB Output is correct
4 Correct 205 ms 49824 KB Output is correct
5 Correct 201 ms 49852 KB Output is correct
6 Correct 203 ms 49804 KB Output is correct
7 Correct 197 ms 49852 KB Output is correct
8 Incorrect 188 ms 49792 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4948 KB Output is correct
2 Correct 33 ms 4948 KB Output is correct
3 Correct 29 ms 4948 KB Output is correct
4 Correct 30 ms 4948 KB Output is correct
5 Correct 29 ms 4988 KB Output is correct
6 Incorrect 29 ms 5036 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 49936 KB Output is correct
2 Correct 206 ms 49804 KB Output is correct
3 Correct 207 ms 49824 KB Output is correct
4 Correct 205 ms 49824 KB Output is correct
5 Correct 201 ms 49852 KB Output is correct
6 Correct 203 ms 49804 KB Output is correct
7 Correct 197 ms 49852 KB Output is correct
8 Incorrect 188 ms 49792 KB Output isn't correct
9 Halted 0 ms 0 KB -