oj.uz

Submission #651895

# Submission time Handle Problem Language Result Execution time Memory
651895 2022-10-20T12:30:17 Z ymm Park (BOI16_park) C++17
100 / 100
 1158 ms 54104 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;

vector<pair<pll,pii>> dis2;
vector<pair<ll,int>> vis;
int ans[N], vr[N], vent[N];

int par[N];
int rt(int v){return par[v]==v?v:(par[v]=rt(par[v]));}
void unite(int v, int u)
{
	v = rt(v);
	u = rt(u);
	par[u] = v;
}

ll Ox[N], Oy[N], Or[N];
ll W, H;
int n, m;

template<class T>
T sqr(T x){return x*x;}

bool cmp (pll _x, pll _y)
{
	pair<__int128, __int128> x = _x;
	pair<__int128, __int128> y = _y;
	auto mn = min(x.second, y.second);
	x.second -= mn;
	y.second -= mn;
	if (x.first != 0 && y.first != 0) {
		x = {4*sqr(x.second)*x.first, x.first + sqr(x.second)}; // 0, 1e18
		y = {4*sqr(y.second)*y.first, y.first + sqr(y.second)}; // 1e36, 1e18
	}
	if (x.first == 0) {
		x.second -= y.second;
		y.second = 0;
		if (x.second < 0)
			return 1;
		return sqr(x.second) < y.first;
	} else {
		y.second -= x.second;
		x.second = 0;
		if (y.second < 0)
			return 0;
		return x.first < sqr(y.second);
	}
}

bool cmp_wrap(const pair<pll,pii> &x, const pair<pll,pii> &y)
{
	return cmp(x.first, y.first);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	cin >> W >> H;
	Loop (i,0,n) 
		cin >> Ox[i] >> Oy[i] >> Or[i];
	Loop (i,0,m) {
		cin >> vr[i] >> vent[i];
		--vent[i];
	}
	Loop (i,0,n) {
		dis2.push_back({{0, Oy[i] - Or[i]}, {i+4, 0}});
		dis2.push_back({{0, W - Ox[i] - Or[i]}, {i+4, 1}});
		dis2.push_back({{0, H - Oy[i] - Or[i]}, {i+4, 2}});
		dis2.push_back({{0, Ox[i] - Or[i]}, {i+4, 3}});
	}
	Loop (i,0,n) Loop (j,i+1,n) {
		ll sdis = sqr(Ox[i] - Ox[j]) + sqr(Oy[i] - Oy[j]);
		ll dis = - Or[i] - Or[j];
		dis2.push_back({{sdis, dis}, {i+4, j+4}});
	}
	Loop (i,0,m)
		vis.push_back({vr[i], i});
	sort(dis2.rbegin(), dis2.rend(), cmp_wrap);
	sort(vis.rbegin(), vis.rend());
	iota(par, par+N, 0);
	while (vis.size()) {
		auto [r2, i] = vis.back();
		vis.pop_back();
		r2 *= 2;
		while (dis2.size() && cmp(dis2.back().first, {0, r2})) {
			auto [v, u] = dis2.back().second;
			unite(v, u);
			dis2.pop_back();
		}
		int e = vent[i];
		int s0 = rt(e+0 & 3);
		int s1 = rt(e+1 & 3);
		int s2 = rt(e+2 & 3);
		int s3 = rt(e+3 & 3);
		ans[i] |= (1 << (e+0 & 3));
		if (s0 != s1 && s0 != s2 && s0 != s3)
			ans[i] |= (1 << (e+1 & 3));
		if (s0 != s2 && s0 != s3 && s1 != s2 && s1 != s3)
			ans[i] |= (1 << (e+2 & 3));
		if (s3 != s0 && s3 != s1 && s3 != s2)
			ans[i] |= (1 << (e+3 & 3));
	}
	Loop (i,0,m) {
		Loop (j,0,4)
			if (ans[i] & (1 << j))
				cout << j+1;
		cout << '\n';
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:99:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   99 |   int s0 = rt(e+0 & 3);
      |               ~^~
park.cpp:100:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  100 |   int s1 = rt(e+1 & 3);
      |               ~^~
park.cpp:101:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  101 |   int s2 = rt(e+2 & 3);
      |               ~^~
park.cpp:102:16: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  102 |   int s3 = rt(e+3 & 3);
      |               ~^~
park.cpp:103:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  103 |   ans[i] |= (1 << (e+0 & 3));
      |                    ~^~
park.cpp:105:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  105 |    ans[i] |= (1 << (e+1 & 3));
      |                     ~^~
park.cpp:107:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  107 |    ans[i] |= (1 << (e+2 & 3));
      |                     ~^~
park.cpp:109:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
  109 |    ans[i] |= (1 << (e+3 & 3));
      |                     ~^~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 49736 KB Output is correct
2 Correct 949 ms 49768 KB Output is correct
3 Correct 943 ms 49788 KB Output is correct
4 Correct 999 ms 49792 KB Output is correct
5 Correct 976 ms 49840 KB Output is correct
6 Correct 1014 ms 49796 KB Output is correct
7 Correct 971 ms 49748 KB Output is correct
8 Correct 929 ms 49832 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5540 KB Output is correct
2 Correct 59 ms 5856 KB Output is correct
3 Correct 50 ms 5740 KB Output is correct
4 Correct 54 ms 5876 KB Output is correct
5 Correct 69 ms 5860 KB Output is correct
6 Correct 53 ms 5820 KB Output is correct
7 Correct 46 ms 5004 KB Output is correct
8 Correct 43 ms 5080 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 49736 KB Output is correct
2 Correct 949 ms 49768 KB Output is correct
3 Correct 943 ms 49788 KB Output is correct
4 Correct 999 ms 49792 KB Output is correct
5 Correct 976 ms 49840 KB Output is correct
6 Correct 1014 ms 49796 KB Output is correct
7 Correct 971 ms 49748 KB Output is correct
8 Correct 929 ms 49832 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 54 ms 5540 KB Output is correct
12 Correct 59 ms 5856 KB Output is correct
13 Correct 50 ms 5740 KB Output is correct
14 Correct 54 ms 5876 KB Output is correct
15 Correct 69 ms 5860 KB Output is correct
16 Correct 53 ms 5820 KB Output is correct
17 Correct 46 ms 5004 KB Output is correct
18 Correct 43 ms 5080 KB Output is correct
19 Correct 1158 ms 54104 KB Output is correct
20 Correct 1040 ms 53972 KB Output is correct
21 Correct 966 ms 54096 KB Output is correct
22 Correct 1029 ms 53972 KB Output is correct
23 Correct 953 ms 53980 KB Output is correct
24 Correct 974 ms 54064 KB Output is correct