제출 #351803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351803		8e7	Park (BOI16_park)	C++14	100 / 100	895 ms	50084 KiB

park

//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);
	return (s - rad[x] - rad[y]) / 2 + 1;
}

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]) / 2 + 1));
		ed.push_back(edge(i, rs, (w - (pos[i].ff + rad[i])) / 2 + 1));
		ed.push_back(edge(i, us, (pos[i].ss - rad[i]) / 2 + 1));
		ed.push_back(edge(i, ds, (h - (pos[i].ss + rad[i])) / 2 + 1));
	}
	sort(ed.begin(), ed.end(), cmp);

	for (int i = 0;i < ed.size();i++) {
		Union(ed[i].u, ed[i].v);
		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]);
	//cout << cross << " " << c1 << " " << c2 << endl;
	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";
	}
}
/*
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

1 10
5 5
3 3 1
1 1

d3c
0 1
a2b
 */

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'int main()':
park.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0;i < ed.size();i++) {
      |                 ~~^~~~~~~~~~~

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