Submission #253233

#	Time	Username	Problem	Language	Result	Execution time	Memory
253233		Blagojce	Park (BOI16_park)	C++11	0 / 100	3 ms	6656 KiB

park

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 3005;
const int mxm = 2e5;

int n, m;
ll w, h;
ll x[mxn], y[mxn], r[mxn];
ld dist[mxn][mxn];

ll rr[mxm];
int e[mxm];

int link[mxn];

ld d(int i, int j){
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
bool ok[(1<<4)];
void mark(int u){
	fr(i, 0, (1<<4)){
		if((i&u)==i) ok[i] = true;
	}
}

int par[mxn];
int siz[mxn];
int findx(int x){
	while(x!=par[x]) x = par[x];
	return x;
}

int unite(int a, int b){
	a = findx(a);
	b = findx(b);
	
	if(a == b) return link[a];
	if(siz[a] < siz[b]) swap(a, b);
	par[b] = a;
	link[a] |= link[b];
	siz[a] += siz[b];
	return link[a];
}


string out_p[mxm];

void solve(){
	fr(i, 0, mxn) siz[i] = 1, par[i] = i;
	
	cin >> n >> m;
	cin >> w >> h;
	fr(i, 0, n){
		cin >> x[i] >> y[i] >> r[i];
	}
	fr(i, 0, n){
		fr(j, i+1, n){
			dist[i][j] = d(i, j) - r[i] - r[j];
		}
	}
	
	fr(i, 0, m){
		cin >> rr[i] >> e[i];
	}
	
	vector<int> p;
	fr(i, 0, m){
		p.pb(i);
	}
	sort(all(p), [](const int &a, const int &b){
		return rr[a] < rr[b];
	});
	
	fr(i, 0, n){
		dist[i][n] = y[i] - r[i];
		dist[i][n+1] = w-x[i]-r[i];
		dist[i][n+2] = h-y[i]-r[i];
		dist[i][n+3] = x[i]-r[i];
	}
	vector<pii> v;
	fr(i, 0, n){
		fr(j, i+1, n+4){
			v.pb({i, j});
		}
	}
	sort(all(v), [](const pii &a, const pii &b){
		return dist[a.st][a.nd] < dist[b.st][b.nd];
	});
	fr(i, n, n+4) link[i] = (1<<(i-n));
	
	int pos = 0;
	
	vector<int> g[5][5];
	int ver = 5, hor = 10;
	int _1 = 9, _2 = 3, _3 = 6, _4 = 12;
	
	g[1][2] = g[2][1] = {ver, _1, _2};
	g[1][3] = g[3][1] = {ver, hor, _1, _3};
	g[1][4] = g[4][1] = {hor, _1, _4};
	
	g[2][3] = g[3][2] = {hor, _2, _3};
	g[2][4] = g[4][2] = {ver, hor, _2, _4};
	
	g[3][4] = g[4][3] = {ver, _3, _4};

	for(auto u : p){
		ld tempr = 2*rr[u];
		while(pos < (int)v.size() && dist[v[pos].st][v[pos].nd] < tempr){
			int a = v[pos].st;
			int b = v[pos].nd;
			
			++pos;
			mark(unite(a, b));
		}
		string o = "";
		fr(i, 1, 5){
			if(i == e[u]){
				o += (char)(i+'0');
			}
			else{
				bool ok2 = true;
				for(auto u2 : g[i][e[u]]){
					if(ok[u2]){
						ok2 = false;
						break;
					}
				}
				if(ok2){
					o += (char)(i+'0');
				}
			
			}
		}
		
		out_p[u] = o;	
	}
	fr(i, 0, m){
		cout<<out_p[i]<<endl;
	}
} 


 
int main(){
	freopen("t.in.11", "r",stdin);
	solve();
}/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:166:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("t.in.11", "r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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