oj.uz

Submission #253234

# Submission time Handle Problem Language Result Execution time Memory
253234 2020-07-27T14:05:56 Z Blagojce Park (BOI16_park) C++11
100 / 100
 1278 ms 65468 KB 
#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
*/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 931 ms 62820 KB Output is correct
2 Correct 917 ms 62816 KB Output is correct
3 Correct 912 ms 62816 KB Output is correct
4 Correct 907 ms 62816 KB Output is correct
5 Correct 914 ms 62816 KB Output is correct
6 Correct 921 ms 62816 KB Output is correct
7 Correct 802 ms 62800 KB Output is correct
8 Correct 694 ms 62816 KB Output is correct
9 Correct 4 ms 6656 KB Output is correct
10 Correct 3 ms 6656 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 10100 KB Output is correct
2 Correct 292 ms 11120 KB Output is correct
3 Correct 303 ms 11176 KB Output is correct
4 Correct 294 ms 11120 KB Output is correct
5 Correct 294 ms 11248 KB Output is correct
6 Correct 289 ms 11296 KB Output is correct
7 Correct 291 ms 10096 KB Output is correct
8 Correct 285 ms 9836 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 931 ms 62820 KB Output is correct
2 Correct 917 ms 62816 KB Output is correct
3 Correct 912 ms 62816 KB Output is correct
4 Correct 907 ms 62816 KB Output is correct
5 Correct 914 ms 62816 KB Output is correct
6 Correct 921 ms 62816 KB Output is correct
7 Correct 802 ms 62800 KB Output is correct
8 Correct 694 ms 62816 KB Output is correct
9 Correct 4 ms 6656 KB Output is correct
10 Correct 3 ms 6656 KB Output is correct
11 Correct 301 ms 10100 KB Output is correct
12 Correct 292 ms 11120 KB Output is correct
13 Correct 303 ms 11176 KB Output is correct
14 Correct 294 ms 11120 KB Output is correct
15 Correct 294 ms 11248 KB Output is correct
16 Correct 289 ms 11296 KB Output is correct
17 Correct 291 ms 10096 KB Output is correct
18 Correct 285 ms 9836 KB Output is correct
19 Correct 1194 ms 65376 KB Output is correct
20 Correct 1190 ms 65468 KB Output is correct
21 Correct 1278 ms 65376 KB Output is correct
22 Correct 1225 ms 65376 KB Output is correct
23 Correct 1211 ms 65376 KB Output is correct
24 Correct 1079 ms 65372 KB Output is correct