oj.uz

Submission #260039

# Submission time Handle Problem Language Result Execution time Memory
260039 2020-08-09T05:06:26 Z arnold518 Park (BOI16_park) C++14
100 / 100
 391 ms 39320 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 35660 KB Output is correct
2 Correct 273 ms 35660 KB Output is correct
3 Correct 285 ms 35668 KB Output is correct
4 Correct 271 ms 35696 KB Output is correct
5 Correct 282 ms 35900 KB Output is correct
6 Correct 277 ms 35644 KB Output is correct
7 Correct 257 ms 35668 KB Output is correct
8 Correct 248 ms 35660 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 8112 KB Output is correct
2 Correct 101 ms 8032 KB Output is correct
3 Correct 103 ms 8048 KB Output is correct
4 Correct 106 ms 8040 KB Output is correct
5 Correct 102 ms 8048 KB Output is correct
6 Correct 104 ms 8048 KB Output is correct
7 Correct 87 ms 7672 KB Output is correct
8 Correct 83 ms 7672 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 35660 KB Output is correct
2 Correct 273 ms 35660 KB Output is correct
3 Correct 285 ms 35668 KB Output is correct
4 Correct 271 ms 35696 KB Output is correct
5 Correct 282 ms 35900 KB Output is correct
6 Correct 277 ms 35644 KB Output is correct
7 Correct 257 ms 35668 KB Output is correct
8 Correct 248 ms 35660 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 113 ms 8112 KB Output is correct
12 Correct 101 ms 8032 KB Output is correct
13 Correct 103 ms 8048 KB Output is correct
14 Correct 106 ms 8040 KB Output is correct
15 Correct 102 ms 8048 KB Output is correct
16 Correct 104 ms 8048 KB Output is correct
17 Correct 87 ms 7672 KB Output is correct
18 Correct 83 ms 7672 KB Output is correct
19 Correct 380 ms 39224 KB Output is correct
20 Correct 391 ms 39152 KB Output is correct
21 Correct 373 ms 39320 KB Output is correct
22 Correct 369 ms 39320 KB Output is correct
23 Correct 358 ms 39320 KB Output is correct
24 Correct 349 ms 39320 KB Output is correct