Submission #260039

#	Time	Username	Problem	Language	Result	Execution time	Memory
260039		arnold518	Park (BOI16_park)	C++14	100 / 100	391 ms	39320 KiB

park

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXM = 1e5;
const ll INF = 1e9;

struct Circle
{
	ll x, y, r;
};

struct Query
{
	ll r; int e, p;
	bool operator < (const Query &q) { return r<q.r; }
};

struct Edge
{
	int u, v; ll w;
	bool operator < (const Edge &p) { return w<p.w; }
};

int N, M;
ll W, H;
Circle A[MAXN+10];
Query B[MAXM+10];
vector<int> ans[MAXM+10];

int par[MAXN+10];

int Find(int x)
{
	if(x==par[x]) return x;
	return par[x]=Find(par[x]);
}

void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	if(x==y) return;
	par[x]=y;
}

bool F[5][5];

int main()
{
	scanf("%d%d", &N, &M);
	scanf("%lld%lld", &W, &H);

	for(int i=1; i<=N+4; i++) par[i]=i;

	for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i].x, &A[i].y, &A[i].r);
	for(int i=1; i<=M; i++) scanf("%lld%d", &B[i].r, &B[i].e), B[i].p=i;
	sort(B+1, B+M+1);
	
	vector<Edge> V;
	for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++)
	{
		ll t=1+(sqrt((A[i].x-A[j].x)*(A[i].x-A[j].x)+(A[i].y-A[j].y)*(A[i].y-A[j].y))-A[i].r-A[j].r)/2; t=max(0ll, t);
		V.push_back({i, j, t});
	}
	for(int i=1; i<=N; i++)
	{
		ll t;
		t=1+(A[i].y-A[i].r)/2; t=max(t, 0ll);
		V.push_back({i, N+1, t});
		t=1+(W-A[i].x-A[i].r)/2; t=max(t, 0ll);
		V.push_back({i, N+2, t});
		t=1+(H-A[i].y-A[i].r)/2; t=max(t, 0ll);
		V.push_back({i, N+3, t});
		t=1+(A[i].x-A[i].r)/2; t=max(t, 0ll);
		V.push_back({i, N+4, t});
	}

	sort(V.begin(), V.end());
	//for(auto it : V) printf("%d %d : %lld\n", it.u, it.v, it.w);

	for(int i=1, j=0; i<=M; i++)
	{
		for(; j<V.size() && V[j].w<=B[i].r; j++) Union(V[j].u, V[j].v);
		
		for(int p=1; p<=4; p++) for(int q=1; q<=4; q++)
		{
			if(Find(N+p)==Find(N+q)) F[p][q]=1;
			else F[p][q]=0;
		}

		if(B[i].e==1)
		{
			ans[B[i].p].push_back(1);
			if(!(F[1][2] || F[1][3] || F[1][4])) ans[B[i].p].push_back(2);
			if(!(F[1][3] || F[1][4] || F[2][3] || F[2][4])) ans[B[i].p].push_back(3);
			if(!(F[4][1] || F[4][2] || F[4][3])) ans[B[i].p].push_back(4);
		}
		else if(B[i].e==2)
		{
			if(!(F[1][2] || F[1][3] || F[1][4])) ans[B[i].p].push_back(1);
			ans[B[i].p].push_back(2);
			if(!(F[2][1] || F[2][3] || F[2][4])) ans[B[i].p].push_back(3);
			if(!(F[1][3] || F[1][2] || F[3][4] || F[2][4])) ans[B[i].p].push_back(4);
		}
		else if(B[i].e==3)
		{
			if(!(F[1][3] || F[1][4] || F[2][3] || F[2][4])) ans[B[i].p].push_back(1);
			if(!(F[2][1] || F[2][3] || F[2][4])) ans[B[i].p].push_back(2);
			ans[B[i].p].push_back(3);
			if(!(F[3][1] || F[3][2] || F[3][4])) ans[B[i].p].push_back(4);
		}
		else
		{
			if(!(F[4][1] || F[4][2] || F[4][3])) ans[B[i].p].push_back(1);
			if(!(F[1][3] || F[1][2] || F[3][4] || F[2][4])) ans[B[i].p].push_back(2);
			if(!(F[3][1] || F[3][2] || F[3][4])) ans[B[i].p].push_back(3);
			ans[B[i].p].push_back(4);		
		}
	}
	for(int i=1; i<=M; i++)
	{
		for(auto it : ans[i]) printf("%d", it);
		printf("\n");
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:87:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<V.size() && V[j].w<=B[i].r; j++) Union(V[j].u, V[j].v);
         ~^~~~~~~~~
park.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
park.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &W, &H);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
park.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i].x, &A[i].y, &A[i].r);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:60:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=M; i++) scanf("%lld%d", &B[i].r, &B[i].e), B[i].p=i;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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