Submission #944648

#	Time	Username	Problem	Language	Result	Execution time	Memory
944648		thefless	Park (BOI16_park)	C++14	0 / 100	1286 ms	3164 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define Times (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define base 31
#define sz(x) (int)(x).size()
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()

#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
#define task "name" 
#define tsk "" 

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int MOD2 = 1e9 + 696969;
const int N = 2e5 + 3;
const int BASE = 10;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

struct DSU{
	vector<int> par;
	DSU(int n = 0): par(n + 7 , -1) {}
	int get(int v){return par[v] < 0 ? v : par[v] = get(par[v]);}
	bool same_set(int a , int b){return get(a) == get(b);}
	bool unite(int a , int b){
		a = get(a); b = get(b);
		if(a == b) return 0;
		par[a] += par[b];
		par[b] = a;
		return 1;
	}
}dsu;
int n , m , w , h;
int square[5];
int cango[5][5];
vector<pii> need_check[5][5];
struct point
{
	int x , y , r;
	point(int x = 0 , int y = 0 , int r = 0): x{x} , y{y} , r{r} {}
}tree[N];

ll sqr(ll x){return x * x;}
double dist(point u , point v){
	double f = u.r + v.r;
	return sqrt(sqr(u.x - v.x) + sqr(u.y - v.y)) - f;
}
ll dist1(point u , point v){
	int f = u.r + v.r;
	return max(0.0 , sqrt(sqr(u.x - v.x) + sqr(u.y - v.y)) - f);
}
bool check(int x , int num){
	for(int i = 1 ; i <= n ; i++){
		if(num == 1){
			if(dist(point(w - x , x , x) , tree[i]) < 0) return 0;
		}
		if(num == 2){
			if(dist(point(w - x , h - x , x) , tree[i]) < 0) return 0;
		}
		if(num == 3){
			if(dist(point(x , h - x , x) , tree[i]) < 0) return 0;
		}
		if(num == 4){
			if(dist(point(x , x , x) , tree[i]) < 0) return 0;
		}
	}
	return 1;
}

int cnp1(int l , int r , int num){
	while(1){
		if(l == r) return l;
		if(r - l == 1){
			if(check(r , num)) return r;
			return l;
		}
		int mid = l + r >> 1;
		if(check(mid , num)) l = mid;
		else r = mid;
	}
}

bool kt(int x , int c , int d){
	dsu = DSU(n);
	for(int i = 1 ; i <= n ; i++){
		if(tree[i].x - tree[i].r < x) dsu.unite(i , n + 1);
		if(tree[i].y - tree[i].r < x) dsu.unite(i , n + 2);
		if(w - (tree[i].x + tree[i].r) < x) dsu.unite(i , n + 3);
		if(h - (tree[i].y + tree[i].r) < x) dsu.unite(i , n + 4);
	}
	for(int i = 2 ; i <= n ; i++){
		for(int j = 1 ; j < i ; j++){
			if(dist(tree[i] , tree[j]) < x) dsu.unite(i , j);
		}
	}

	for(auto x : need_check[min(c , d)][max(c , d)]){
		if(dsu.same_set(n + x.fi , n + x.se)) return 0;
	}
	return 1;
}
int cnp2(int l , int r , int c , int d){
	while(1){
		if(l == r) return l;
		if(r - l == 1){
			if(kt(2 * r , c , d)) return r;
			return l;
		}
		int mid = l + r >> 1;
		if(kt(2 * mid , c , d)) l = mid;
		else r = mid;
	}
}
void Solve(){
	cin >> n >> m;
	cin >> w >> h;
	for(int i = 1 ; i <= n ; i++){
		cin >> tree[i].x >> tree[i].y >> tree[i].r;
	}
	for(int i = 1 ; i <= 4 ; i++){
		square[i] = cnp1(0 , min(w , h) , i);
	}
	need_check[1][2] = vector<pii>({{1 , 4} , {2 , 4} , {3 , 4}});
	need_check[1][3] = vector<pii>({{1 , 3} , {2 , 4} , {2 , 3} , {1 , 4}});
	need_check[1][4] = vector<pii>({{1 , 2} , {1 , 3} , {1 , 4}});
	need_check[2][3] = vector<pii>({{3 , 1} , {3 , 2} , {3 , 4}});
	need_check[2][4] = vector<pii>({{1 , 3} , {2 , 4} , {1 , 2} , {3 , 4}});
	need_check[3][4] = vector<pii>({{2 , 4} , {1 , 2} , {3 , 2}});
	for(int i = 1 ; i <= 4 ; i++){
		for(int j = 1 ; j < i ; j++){
			cango[i][j] = cango[j][i] = cnp2(0 , min(w , h) , j , i);
		}
	}
	for(int i = 1 ; i <= 4 ; i++) cango[i][i] = square[i];
	for(int k = 1 ; k <= 4 ; k++){
		for(int i = 1 ; i <= 4 ; i++){
			for(int j = 1 ; j <= 4 ; j++) maximize(cango[i][j] , min(cango[i][k] , cango[k][j]));
		}
	}
	while(m--){
		int x , r;
		cin >> r >> x;
		for(int i = 1 ; i <= 4 ; i++){
			if(cango[i][x] >= r) cout << i;
		}
		cout << '\n';
	}
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    file(task);
    file(tsk);
    int T = 1;
    // cin >> T;
    while(T--)
    {
        Solve();
    }
    cerr << "Time elapsed: " << Times << " s.\n";
    return 0;
}
// author: thefless
// I love Kim Anh

Compilation message (stderr)

park.cpp: In function 'int cnp1(int, int, int)':
park.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int mid = l + r >> 1;
      |             ~~^~~
park.cpp: In function 'int cnp2(int, int, int, int)':
park.cpp:119:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |   int mid = l + r >> 1;
      |             ~~^~~
park.cpp: In function 'int main()':
park.cpp:16:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:163:5: note: in expansion of macro 'file'
  163 |     file(task);
      |     ^~~~
park.cpp:16:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:163:5: note: in expansion of macro 'file'
  163 |     file(task);
      |     ^~~~
park.cpp:16:125: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:163:5: note: in expansion of macro 'file'
  163 |     file(task);
      |     ^~~~
park.cpp:16:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:164:5: note: in expansion of macro 'file'
  164 |     file(tsk);
      |     ^~~~
park.cpp:16:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:164:5: note: in expansion of macro 'file'
  164 |     file(tsk);
      |     ^~~~
park.cpp:16:125: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
      |                                                                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:164:5: note: in expansion of macro 'file'
  164 |     file(tsk);
      |     ^~~~

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