제출 #257191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257191		Berted	Park (BOI16_park)	C++14	100 / 100	509 ms	25664 KiB

park

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppi pair<pii, int>
#define pip pair<int, pii>
using namespace std;

const int INF = 1e9 + 7;

int n, m, w, h, par[15000];
vector<ppi> coord;
vector<pip> edge;

int fn(int a) {return par[a] = (par[a] == a) ? a : fn(par[a]);}
void jn(int a, int b)
{
	a = fn(a), b = fn(b);
	if (a != b) {par[b] = a;}
}
inline int getDist(int a, int b)
{
	return floor(hypot(coord[a].fst.fst - coord[b].fst.fst, coord[a].fst.snd - coord[b].fst.snd) - coord[a].snd - coord[b].snd);
}

int l, r, u, d;
int lol[6] = {INF, INF, INF, INF, INF, INF};

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	cin >> w >> h;

	for (int i = 0; i < n; i++)
	{
		int x, y, r; cin >> x >> y >> r;
		coord.push_back({{x, y}, r});
		edge.push_back({x - r, {i, n}});
		edge.push_back({w - x - r, {i, n + 1}});
		edge.push_back({y - r, {i, n + 3}});
		edge.push_back({h - y - r, {i, n + 2}});
	}
	for (int i = 0; i < coord.size() + 4; i++) {par[i] = i;}
	l = coord.size(); r = coord.size() + 1;
	u = coord.size() + 2; d = coord.size() + 3;
	for (int i = 0; i < coord.size(); i++)
	{
		for (int j = i + 1; j < coord.size(); j++)
		{
			edge.push_back({getDist(i, j), {i, j}});
		}
	}
	sort(edge.begin(), edge.end());
	for (const auto &x : edge)
	{
		jn(x.snd.fst, x.snd.snd);
		//cout << "Joining " << x.snd.fst << " " << x.snd.snd << " " << x.fst << "\n";
		if (fn(l) == fn(d) && lol[0] == INF) 
		{
			lol[0] = x.fst;
			//cout << "0 " << lol[0] << "\n";
		}
		if (fn(d) == fn(r) && lol[1] == INF) 
		{
			lol[1] = x.fst;
			//cout << "1 " << lol[1] << "\n";
		}
		if (fn(r) == fn(u) && lol[2] == INF) 
		{
			lol[2] = x.fst;
			//cout << "2 " << lol[2] << "\n";
		}
		if (fn(u) == fn(l) && lol[3] == INF) 
		{
			lol[3] = x.fst;
			//cout << "3 " << lol[3] << "\n";
		}
		if (fn(u) == fn(d) && lol[4] == INF) 
		{
			lol[4] = x.fst;
			//cout << "4 " << lol[4] << "\n";
		}
		if (fn(l) == fn(r) && lol[5] == INF) 
		{
			lol[5] = x.fst;
			//cout << "5 " << lol[5] << "\n";
		}
	}
	for (int i = 0; i < m; i++)
	{
		int s, r; cin >> r >> s; s--; r *= 2;
		string res = "";
		for (int j = 0; j < 4; j++)
		{
			if (j == s) res.push_back((char)(j + '1'));
			else
			{
				int mn = min(lol[j], lol[s]);
				//cout << mn << "\n";
				if (abs(j - s) == 2) {mn = min(mn, min(lol[4], lol[5]));}
				else if ((s + 1) % 4 == j) 
				{
					if (s % 2 == 0) mn = min(mn, lol[4]);
					else mn = min(mn, lol[5]);
				}
				else
				{
					if (s % 2 == 0) mn = min(mn, lol[5]);
					else mn = min(mn, lol[4]);
				}
				//cout << s << " " << j << " " << mn << "\n";
				if (r <= mn) res.push_back((char)(j + '1'));
			}
		}
		cout << res << "\n";
	}
	return 0;
}

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

park.cpp: In function 'int main()':
park.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < coord.size() + 4; i++) {par[i] = i;}
                  ~~^~~~~~~~~~~~~~~~~~
park.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < coord.size(); i++)
                  ~~^~~~~~~~~~~~~~
park.cpp:52:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j < coord.size(); j++)
                       ~~^~~~~~~~~~~~~~

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