Submission #501211

#	Time	Username	Problem	Language	Result	Execution time	Memory
501211		Arnch	Park (BOI16_park)	C++17	100 / 100	475 ms	61844 KiB

park

// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long long ld;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

struct tree {
	ll x, y, r;
} x[N];

ll r[N], e[N];
int par[N], sz[N];
bool flag[5];

vector<tuple<int, int, ld> > vc;
vector<int> Q;
vector<int> ans[N];

bool cmp(tuple<int, int, ld> i, tuple<int, int, ld> j) {
	return get<2>(i) < get<2>(j);
}
bool cmp2(int i, int j) {
	return r[i] < r[j];
}

int get_root(int u) {
	if(par[u] == u) return u;
	return par[u] = get_root(par[u]);
}
void merge(int u, int v) {
	int U = get_root(u), V = get_root(v);
	if(U == V) return;

	if(sz[U] < sz[V]) swap(U, V);
	sz[U] += sz[V];
	par[V] = U;
}

void dojob(int type) {
	int X0 = get_root(0), X1 = get_root(1), X2 = get_root(2), X3 = get_root(3);
	if(type == 1) {
		if(X0 == X3 || X0 == X2 || X3 == X1 || X1 == X2) flag[3] = 1;
		if(X0 == X1 || X0 == X2 || X0 == X3) flag[2] = 1;
		if(X3 == X0 || X3 == X2 || X3 == X1) flag[4] = 1;
		return;
	}
	if(type == 2) {
		if(X0 == X1 || X0 == X2 || X1 == X3 || X2 == X3) flag[4] = 1;
		if(X0 == X1 || X0 == X2 || X0 == X3) flag[1] = 1;
		if(X1 == X2 || X1 == X0 || X1 == X3) flag[3] = 1;
		return;
	}
	if(type == 3) {
		if(X0 == X3 || X0 == X2 || X3 == X1 || X1 == X2) flag[1] = 1;
		if(X1 == X0 || X1 == X2 || X1 == X3) flag[2] = 1;
		if(X2 == X0 || X2 == X1 || X2 == X3) flag[4] = 1;
		return;
	}
	if(type == 4) {
		if(X0 == X1 || X0 == X2 || X1 == X3 || X2 == X3) flag[2] = 1;
		if(X2 == X0 || X2 == X1 || X2 == X3) flag[3] = 1;
		if(X3 == X0 || X3 == X1 || X3 == X2) flag[1] = 1;
		return;
	}
}


int main() {
    fast_io;

	int n, m; cin >>n >>m;
	int w, h; cin >>w >>h;
	for(int i = 4; i < n + 4; i++) {
		cin >>x[i].x >>x[i].y >>x[i].r;
		vc.push_back({0, i, x[i].y - x[i].r});
		vc.push_back({1, i, w - x[i].x - x[i].r});
		vc.push_back({2, i, h - x[i].y - x[i].r});
		vc.push_back({3, i, x[i].x - x[i].r});
	}
	
	for(int i = 4; i < n + 4; i++)
		for(int j = i + 1; j < n + 4; j++) {
			ll valx = abs(x[i].x - x[j].x); valx *= valx;
			ll valy = abs(x[i].y - x[j].y); valy *= valy;
			ld val = sqrt((valx + valy)) - x[i].r - x[j].r;
			vc.push_back({i, j, val});
		}
	
	sort(all(vc), cmp);

	for(int i = 0; i < m; i++) {
		cin >>r[i] >>e[i];
		Q.push_back(i);
	}
	sort(all(Q), cmp2);

	for(int i = 0; i < n + 4; i++)
		par[i] = i, sz[i] = 1;

	int ind = 0;
	for(auto i : Q) {
		while(ind < Sz(vc) && get<2>(vc[ind]) < (ld)2 * r[i]) {
			int u = get<0>(vc[ind]), v = get<1>(vc[ind]);

	//		cout<<"^^^"<<u <<" " <<v <<" " <<get<2>(vc[ind]) <<" " <<i <<endl;
			merge(u, v);
			ind++;
		}
		memset(flag, 0, sizeof(flag));
		dojob(e[i]);
		for(int j = 1; j <= 4; j++)
			if(!flag[j]) ans[i].push_back(j);
	}

	for(int i = 0; i < m; i++) {
		for(auto j : ans[i])
			cout<<j;
		cout<<"\n";
	}

    return 0;
}

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