oj.uz

Submission #253225

# Submission time Handle Problem Language Result Execution time Memory
253225 2020-07-27T13:37:24 Z Blagojce Park (BOI16_park) C++11
27 / 100
 538 ms 40800 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 = 1e5;

int n, m;
ll w, h;
ll x[mxn], y[mxn], r[mxn];
ll 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];
}



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] = floor(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){
		ll 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));
		}
		fr(i, 1, 5){
			if(i == e[u]){
				cout<<i;
			}
			else{
				bool ok2 = true;
				for(auto u2 : g[i][e[u]]){
					if(ok[u2]){
						ok2 = false;
						break;
					}
				}
				if(ok2){
					cout<<i;
				}
			}
		}
		cout<<endl;	
	}
} 


 
int main(){
	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 522 ms 40796 KB Output is correct
2 Correct 514 ms 40800 KB Output is correct
3 Correct 505 ms 40800 KB Output is correct
4 Correct 513 ms 40800 KB Output is correct
5 Correct 502 ms 40800 KB Output is correct
6 Correct 538 ms 40800 KB Output is correct
7 Correct 449 ms 40800 KB Output is correct
8 Correct 371 ms 40800 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 3816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 40796 KB Output is correct
2 Correct 514 ms 40800 KB Output is correct
3 Correct 505 ms 40800 KB Output is correct
4 Correct 513 ms 40800 KB Output is correct
5 Correct 502 ms 40800 KB Output is correct
6 Correct 538 ms 40800 KB Output is correct
7 Correct 449 ms 40800 KB Output is correct
8 Correct 371 ms 40800 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Incorrect 295 ms 3816 KB Output isn't correct
12 Halted 0 ms 0 KB -