Submission #236757

#	Time	Username	Problem	Language	Result	Execution time	Memory
236757		BamiTorabi	Park (BOI16_park)	C++14	100 / 100	700 ms	33528 KiB

park

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef pair <ll, pii> edge;

const int maxN = 2e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int arumin[4][4], m, par[maxN];
int X[maxN], Y[maxN], rad[maxN];
edge E[maxN * maxN];

ll SQ(ll x){
	ll lt = 0, rt = MOD;
	while (rt - lt > 1){
		ll md = (lt + rt) >> 1;
		(md * md > x ? rt : lt) = md;
	}
	return rt;
}

ll dist(int a, int b){
	ll x = X[a] - X[b];
	ll y = Y[a] - Y[b];
	return SQ(x * x + y * y);
}

int getpar(int v){
	return (par[v] == v ? v : par[v] = getpar(par[v]));
}

void join(int u, int v){
	u = getpar(u);
	v = getpar(v);
	par[u] = v;
	return;
}

void put(int a, int b, int x){
	arumin[a][b] = min(arumin[a][b], x);
	arumin[b][a] = min(arumin[b][a], x);
	return;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	iota(par, par + maxN, 0);
	int n, q; scanf("%d%d", &n, &q);
	int w, h; scanf("%d%d", &w, &h);
	E[m++] = {w, {0, 2}};
	E[m++] = {h, {1, 3}};
	for (int i = 4; i < n + 4; i++){
		scanf("%d%d%d", X + i, Y + i, rad + i);
		E[m++] = {X[i] - rad[i], {0, i}};
		E[m++] = {Y[i] - rad[i], {1, i}};
		E[m++] = {w - X[i] - rad[i], {2, i}};
		E[m++] = {h - Y[i] - rad[i], {3, i}};
		for (int j = 4; j < i; j++)
			E[m++] = {dist(j, i) - rad[i] - rad[j], {j, i}};
	}
	sort(E, E + m);
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			arumin[i][j] = MOD;
	for (int x = 0; x < m; x++){
		int d, a, b; pii pp;
		tie(d, pp) = E[x];
		tie(a, b) = pp;
		join(a, b);
		for (int i = 0; i < 4; i++)
			for (int j = i + 1; j < 4; j++)
				if (getpar(i) == getpar(j)){
					if ((4 + i - j) & 1){
						for (int k = 0; k < 4; k++)
							if ((i == 0 && j == 3 ? j : i) != k)
								put((i == 0 && j == 3 ? j : i), k, d);
					}
					else{
						for (int k = 0; k < 2; k++)
							for (int l = 0; l < 2; l++)
								put((i + k) & 3, (j + l) & 3, d);
					}
				}
	}
	while (q--){
		int r, p; scanf("%d%d", &r, &p);
		p--; r <<= 1;
		for (int i = 0; i < 4; i++)
			if (r < arumin[p][i])
				printf("%d", i + 1);
		printf("\n");
	}
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}
 

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:72:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q; scanf("%d%d", &n, &q);
            ~~~~~^~~~~~~~~~~~~~~~
park.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int w, h; scanf("%d%d", &w, &h);
            ~~~~~^~~~~~~~~~~~~~~~
park.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", X + i, Y + i, rad + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int r, p; scanf("%d%d", &r, &p);
             ~~~~~^~~~~~~~~~~~~~~~

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