oj.uz

Submission #257266

# Submission time Handle Problem Language Result Execution time Memory
257266 2020-08-04T03:03:40 Z super_j6 Park (BOI16_park) C++14
100 / 100
 366 ms 49840 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define f first
#define s second
#define sq(x) ((x) * (x))

const int mxn = 2000, mxm = 100000, k = 4;
int n, m, w[2];
int a[mxn][2], r[mxn];
int par[mxn + k], rnk[mxn + k];
vector<pii> v;
bool ans[mxm][k];

int fnd(int x){
	return x == par[x] ? x : par[x] = fnd(par[x]);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < 2; i++) cin >> w[i];
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 2; j++) cin >> a[i][j];
		cin >> r[i];
		par[i] = i;
		
		for(int j = 0; j < i; j++){
			ll d = 0;
			for(int l = 0; l < 2; l++) d += sq((ll)a[i][l] - a[j][l]);
			v.push_back({(int)sqrtl(d) - r[i] - r[j], {j, i}});
		}
		
		for(int j = 0; j < 2; j++)
		for(int l = 0; l < 2; l++){
			v.push_back({abs(l * w[j] - a[i][j]) - r[i], {i, n + j + 2 * l}});
		}
	}
	for(int i = 0; i < k; i++) par[n + i] = n + i;
	
	for(int i = 0; i < m; i++){
		int qr, x;
		cin >> qr >> x;
		v.push_back({2 * qr, {-x, i}});
	}
	
	sort(v.begin(), v.end());
	
	for(pii i : v){
		if(i.s.f < 0){
			for(int x[2] = {-i.s.f - 1, 0}; x[1] < k; x[1]++){
				ans[i.s.s][x[1]] = 1;
				if(x[0] == x[1]) continue;
				for(int j = 0; j < 2; j++){
					ans[i.s.s][x[1]] &= fnd(n + x[j]) != fnd(n + (x[j] + 1) % k);
					ans[i.s.s][x[1]] &= (k + x[1] - x[0]) % k == 1 + 2 * j || 
						fnd(n + (x[0] + j) % k) != fnd(n + (x[0] + j + 2) % k);
				}
			}
		}else{
			int x = fnd(i.s.f), y = fnd(i.s.s);
			if(x != y){
				if(rnk[x] < rnk[y]) swap(x, y);
				rnk[x] += rnk[x] == rnk[y];
				par[y] = x;
			}
		}
	}
	
	for(int i = 0; i < m; i++){
		string ret;
		for(int j = 0; j < k; j++) if(ans[i][j]) ret += '1' + j;
		cout << ret << endl;
	}

	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 25172 KB Output is correct
2 Correct 282 ms 25176 KB Output is correct
3 Correct 284 ms 25180 KB Output is correct
4 Correct 276 ms 25184 KB Output is correct
5 Correct 275 ms 25172 KB Output is correct
6 Correct 275 ms 25172 KB Output is correct
7 Correct 255 ms 25208 KB Output is correct
8 Correct 259 ms 25172 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2644 KB Output is correct
2 Correct 48 ms 2664 KB Output is correct
3 Correct 48 ms 2604 KB Output is correct
4 Correct 47 ms 2664 KB Output is correct
5 Correct 48 ms 2668 KB Output is correct
6 Correct 45 ms 2664 KB Output is correct
7 Correct 48 ms 2408 KB Output is correct
8 Correct 49 ms 2412 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 25172 KB Output is correct
2 Correct 282 ms 25176 KB Output is correct
3 Correct 284 ms 25180 KB Output is correct
4 Correct 276 ms 25184 KB Output is correct
5 Correct 275 ms 25172 KB Output is correct
6 Correct 275 ms 25172 KB Output is correct
7 Correct 255 ms 25208 KB Output is correct
8 Correct 259 ms 25172 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 51 ms 2644 KB Output is correct
12 Correct 48 ms 2664 KB Output is correct
13 Correct 48 ms 2604 KB Output is correct
14 Correct 47 ms 2664 KB Output is correct
15 Correct 48 ms 2668 KB Output is correct
16 Correct 45 ms 2664 KB Output is correct
17 Correct 48 ms 2408 KB Output is correct
18 Correct 49 ms 2412 KB Output is correct
19 Correct 347 ms 49708 KB Output is correct
20 Correct 366 ms 49840 KB Output is correct
21 Correct 336 ms 49708 KB Output is correct
22 Correct 333 ms 49836 KB Output is correct
23 Correct 334 ms 49708 KB Output is correct
24 Correct 314 ms 49708 KB Output is correct