Submission #351766

# Submission time Handle Problem Language Result Execution time Memory
351766 2021-01-20T07:36:12 Z 8e7 Park (BOI16_park) C++14
0 / 100
805 ms 49720 KB
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define maxn 2005
#define pii pair<int, int>
#define ff first
#define ss second
#define ll long long
using namespace std;
pii pos[maxn];
int rad[maxn], par[maxn], val[4][4], mv[4], cross, c1, c2;
bool done[4][4], ans[4];

const int ls = maxn - 1, rs = maxn - 2, us = maxn - 3, ds = maxn - 4;
inline int dist(int x, int y) {
	ll d = (ll)(pos[x].ff - pos[y].ff) * (pos[x].ff - pos[y].ff) + (ll)(pos[x].ss - pos[y].ss) * (pos[x].ss - pos[y].ss);
	ll s = sqrt(d);
	if (s * s == d) return (s - rad[x] - rad[y] + 1) / 2;
	else return (s - rad[x] - rad[y] + 2) / 2;
}

struct edge{
	int u, v, d;
	edge(int a, int b, int c) {
		u = a, v = b, d = c;
	}
};
vector<edge> ed;
inline bool cmp(edge a, edge b) {
	return a.d < b.d;
}

inline int find(int a) {
	return a == par[a] ? a : (par[a] = find(par[a]));
}
void Union(int a, int b) {
	par[find(a)] = find(b);
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m, w, h;
	cin >> n >> m >> w >> h;
	for (int i = 0;i < maxn;i++) par[i] = i;
	for (int i = 0;i < 4;i++) mv[i] = 2147483647;
	for (int i = 0;i < n;i++) {
		cin >> pos[i].ff >> pos[i].ss >> rad[i];
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			ed.push_back(edge(i, j, dist(i, j)));
		}
		ed.push_back(edge(i, ls, pos[i].ff - rad[i]));
		ed.push_back(edge(i, rs, w - (pos[i].ff + rad[i])));
		ed.push_back(edge(i, us, pos[i].ss - rad[i]));
		ed.push_back(edge(i, ds, h - (pos[i].ss + rad[i])));
	}
	sort(ed.begin(), ed.end(), cmp);

	for (int i = 0;i < ed.size();i++) {
		Union(ed[i].u, ed[i].v);
		if (ed[i].u > n || ed[i].v > n) {
			for (int j = 1;j <= 4;j++) {
				for (int k = j + 1;k <= 4;k++) {
					if (!done[j - 1][k - 1] && find(maxn - j) == find(maxn - k)) {
						val[j - 1][k - 1] = ed[i].d;
						done[j - 1][k - 1] = 1;
					}
				}
			}
		}
	}
	for (int i = 0;i < 4;i++) {
		for (int j = i + 1;j < 4;j++) {
			mv[i] = min(mv[i], val[i][j]);
			mv[j] = min(mv[j], val[i][j]);
		}
	}
	cross = min(val[0][1], val[2][3]);
	c1 = min(val[0][2], val[1][3]);
	c2 = min(val[1][2], val[0][3]);
	for (int i = 0;i < m;i++) {
		int r, e;
		cin >> r >> e;
		ans[0] = ans[1] = ans[2] = ans[3] = 0;
		ans[e - 1] = 1;
		if (e == 1) {
			if (mv[2] > r) ans[1] = 1;
			if (mv[0] > r) ans[3] = 1;
			if (min(cross, c1) > r) ans[2] = 1;
		} else if (e == 2) {
			if (mv[2] > r) ans[0] = 1;
			if (mv[1] > r) ans[2] = 1;
			if (min(cross, c2) > r) ans[3] = 1;
		} else if (e == 3) {
			if (mv[1] > r) ans[1] = 1;
			if (mv[3] > r) ans[3] = 1;
			if (min(cross, c1) > r) ans[0] = 1;
		} else{
			if (mv[0] > r) ans[0] = 1;
			if (mv[3] > r) ans[2] = 1;
			if (min(cross, c2) > r) ans[1] = 1;
		}
		for (int j = 0;j < 4;j++) {
			if (ans[j]) cout << j + 1;
		}
		cout << "\n";
	}
}
/*
2 2 1000000000 1000000000
0 0 1
300000000 400000000 1


5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

d3c
0 1
a2b
 */

Compilation message

park.cpp: In function 'int main()':
park.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 0;i < ed.size();i++) {
      |                 ~~^~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 805 ms 49720 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 1508 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 805 ms 49720 KB Output isn't correct
2 Halted 0 ms 0 KB -