oj.uz

Submission #379951

# Submission time Handle Problem Language Result Execution time Memory
379951 2021-03-19T19:33:22 Z AriaH Park (BOI16_park) C++11
100 / 100
 706 ms 109444 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const ld one = 1.;
const ld eps = 1e-12;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

ll n, m, w, h, X[N], Y[N], R[N], par[N], sz[N];

int get(int x)
{
	return (x == par[x]? x : par[x] = get(par[x]));
}

void unify(int v, int u)
{
	v = get(v), u = get(u);
	if(v == u) return;
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
}

pair < pll, int > Q[N];

vector < pair < ld, pll > > E;

vector < int > Ans[N];

bool cmp(pair < pll, ll > a, pair < pll, ll > b)
{
	return a.F < b.F;
}

int ok(int a, int b)
{
	a += n;
	b += n;
	return (get(a) == get(b));
}

int can(int a, int b)
{
	if(a == b) return 1;
	if(a > b) swap(a, b);
	if(a == 1 && b == 2)
	{
		return ((ok(1, 2) || ok(2, 4) || ok(2, 3)) == 0);
	}
	if(a == 1 && b == 3)
	{
		return ((ok(1, 2) || ok(1, 3) || ok(2, 4) || ok(3, 4)) == 0);
	}
	if(a == 1 && b == 4)
	{
		return ((ok(1, 2) || ok(1, 3) || ok(1, 4)) == 0);
	}
	if(a == 2 && b == 3)
	{
		return ((ok(1, 3) || ok(2, 3) || ok(4, 3)) == 0);
	}
	if(a == 2 && b == 4)
	{
		return ((ok(1, 3) || ok(1, 4) || ok(2, 3) || ok(2, 4)) == 0);
	}
	else
	{
		return ((ok(1, 4) || ok(2, 4) || ok(3, 4)) == 0);
	}

}

int main()
{
	for(int i = 0; i < N; i ++) sz[i] = 1, par[i] = i;
	scanf("%lld%lld%lld%lld", &n, &m, &w, &h);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]);
		E.push_back(Mp(X[i] - R[i], Mp(n + 1, i)));
		E.push_back(Mp(Y[i] - R[i], Mp(n + 2, i)));
		E.push_back(Mp(w - X[i] - R[i], Mp(n + 3, i)));
		E.push_back(Mp(h - Y[i] - R[i], Mp(n + 4, i)));
		for(int j = 1; j < i; j ++)
		{
			ll dx = abs(X[i] - X[j]), dy = abs(Y[i] - Y[j]);
			ll dist = sqrt(dx * dx + dy * dy) - one * R[i] - one * R[j];
			E.push_back(Mp(dist, Mp(i, j)));
		}
	}
	sort(all(E));
	for(int i = 1; i <= m; i ++)
	{
		scanf("%lld%lld", &Q[i].F.F, &Q[i].F.S);
		Q[i].F.F *= 2;
		Q[i].S = i;
	}
	sort(Q + 1, Q + m + 1, cmp);
	int last = 0;
	for(int i = 1; i <= m; i ++)
	{
		///printf("i = %d Q.F : %lld Q.S : %lld\n", i, Q[i].F.F, Q[i].F.S);
		while(last < SZ(E) && (one * Q[i].F.F - E[last].F) > eps)
		{
			unify(E[last].S.F, E[last].S.S);
			last ++;
		}
		for(int j = 1; j <= 4; j ++)
		{
			if(can(Q[i].F.S, j))
			{
				Ans[Q[i].S].push_back(j);
			}
		}
	}
	for(int i = 1; i <= m; i ++)
	{
		for(auto x : Ans[i])
		{
			printf("%d", x);
		}
		printf("\n");
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

park.cpp: In function 'int main()':
park.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |  scanf("%lld%lld%lld%lld", &n, &m, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |   scanf("%lld%lld%lld", &X[i], &Y[i], &R[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |   scanf("%lld%lld", &Q[i].F.F, &Q[i].F.S);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 105316 KB Output is correct
2 Correct 552 ms 105360 KB Output is correct
3 Correct 553 ms 105360 KB Output is correct
4 Correct 558 ms 105360 KB Output is correct
5 Correct 552 ms 105488 KB Output is correct
6 Correct 555 ms 105360 KB Output is correct
7 Correct 536 ms 105360 KB Output is correct
8 Correct 550 ms 105388 KB Output is correct
9 Correct 25 ms 39532 KB Output is correct
10 Correct 26 ms 39532 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 46048 KB Output is correct
2 Correct 154 ms 46048 KB Output is correct
3 Correct 130 ms 46048 KB Output is correct
4 Correct 132 ms 45920 KB Output is correct
5 Correct 138 ms 46108 KB Output is correct
6 Correct 145 ms 46116 KB Output is correct
7 Correct 115 ms 46444 KB Output is correct
8 Correct 121 ms 46540 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 105316 KB Output is correct
2 Correct 552 ms 105360 KB Output is correct
3 Correct 553 ms 105360 KB Output is correct
4 Correct 558 ms 105360 KB Output is correct
5 Correct 552 ms 105488 KB Output is correct
6 Correct 555 ms 105360 KB Output is correct
7 Correct 536 ms 105360 KB Output is correct
8 Correct 550 ms 105388 KB Output is correct
9 Correct 25 ms 39532 KB Output is correct
10 Correct 26 ms 39532 KB Output is correct
11 Correct 139 ms 46048 KB Output is correct
12 Correct 154 ms 46048 KB Output is correct
13 Correct 130 ms 46048 KB Output is correct
14 Correct 132 ms 45920 KB Output is correct
15 Correct 138 ms 46108 KB Output is correct
16 Correct 145 ms 46116 KB Output is correct
17 Correct 115 ms 46444 KB Output is correct
18 Correct 121 ms 46540 KB Output is correct
19 Correct 671 ms 109416 KB Output is correct
20 Correct 652 ms 109260 KB Output is correct
21 Correct 706 ms 109444 KB Output is correct
22 Correct 665 ms 109412 KB Output is correct
23 Correct 653 ms 109260 KB Output is correct
24 Correct 653 ms 109388 KB Output is correct