oj.uz

Submission #389805

# Submission time Handle Problem Language Result Execution time Memory
389805 2021-04-14T14:33:10 Z Cantfindme Park (BOI16_park) C++17
100 / 100
 1325 ms 139232 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

#define ld long double

typedef pair<ld, pi> pii;
 
const int maxn = 2050;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7; 

int n,Q;
int W, H;

int parent[maxn];
int findp(int x){ 
	if (parent[x] == x) return x;
	return parent[x] = findp(parent[x]);
}

//n -> left wall, n+1, right wall, n+2, up wall, n+3 down wall
//1 = bottom-left, 2 = bottom-right, 3 = top-right, 4 = top-left

map <pi,int> mp;
int isblock[5];

vector <pii> v;
vector <pii> queries;
string rans[100010];

ld calc(pi a, pi b) {
	return sqrt((ld)abs(a.f - b.f) * abs(a.f - b.f) + abs(a.s - b.s) * abs(a.s-b.s));
}

void upblock(int a, int b) {
	if (a > b) swap(a,b);
	if (a == n and b == n+1) { //block left to right
		mp[pi(1,4)] = mp[pi(4,1)] = mp[pi(3,2)] = mp[pi(2,3)] = 1;
		mp[pi(1,3)] = mp[pi(3,1)] = mp[pi(2,4)] = mp[pi(4,2)] = 1;
	}
	
	if (a == n+2 and b == n+3) { //block up to down
		mp[pi(4,3)] = mp[pi(3,4)] = mp[pi(1,2)] = mp[pi(2,1)] = 1;
		mp[pi(4,2)] = mp[pi(2,4)] = mp[pi(1,3)] = mp[pi(3,1)] = 1;
	}
	
	if (a == n and b == n+3) { //block 1
		isblock[1] = 1;
	}
	
	if (a == n+1 and b == n+3) { //block 2
		isblock[2] = 1;
	}
	
	if (a == n+1 and b == n+2) { //block 3
		isblock[3] = 1;
	}
	
	if (a == n and b == n+2) { //block 4
		isblock[4] = 1;
	}
	
}

void check() {
	for (int i = n; i <= n+3; i++) {
		for (int j =i+1;j<=n+3;j++) {
			if (findp(i) == findp(j)) upblock(i,j);
		}
	}
}

void checkans(pii qq) {
	int e = qq.s.f;
	int indx = qq.s.s;
	
	vector <int> ans = {e};

	if (!isblock[e]) {
		for (int j = 1; j <=4;j++) {			
			if (j == e) continue;
			if (isblock[j]) continue;
			if (mp[pi(j,e)]) continue;
			ans.push_back(j);
		}
	}
	
	sort(all(ans));
	rans[indx] = "";
	for (auto i: ans) rans[indx] += to_string(i); 
}

int32_t main() {
	FAST
	cin >> n >> Q;
	cin >> W >> H;
	
	for (int i =0;i<n+4;i++) parent[i] = i;
	
	for (int i =0;i<n;i++) {
		int x,y,r; cin >> x >> y >> r;
		v.push_back(pii(r,pi(x,y)));
	}
	
	for (int i =0;i<Q;i++) {
		int r, e; cin >> r >> e;
		queries.push_back(pii(r,pi(e,i)));
	}
	
	vector <pii> edges;
	
	for (int i =0;i<n;i++) {
		for (int j =0;j<n;j++) {
			if (i == j) continue;
			ld totald = calc(v[i].s, v[j].s);
			edges.push_back(pii(totald - v[i].f - v[j].f, pi(i,j)));
		}
		
		edges.push_back(pii(v[i].s.f - v[i].f, pi(i,n))); //left wall
		edges.push_back(pii(W - v[i].s.f - v[i].f,pi(i,n+1))); //right wall
		edges.push_back(pii(v[i].s.s - v[i].f, pi(i,n+3))); //down wall
		edges.push_back(pii(H - v[i].s.s - v[i].f, pi(i,n+2))); //up wall
	}
	
	sort(all(edges));
	sort(all(queries));
	
	int co = 0;
	for (auto [d, cur] : edges) {
		while (co < Q and queries[co].f*2 <= d) {
			checkans(queries[co]);
			co++;
		}
		
		auto [a,b] = cur;
		if (findp(a) == findp(b)) continue;
		parent[findp(a)] = findp(b);
	
		check();
	}
	
	while (co < Q) {
		checkans(queries[co]);
		co++;
	}
	
	for (int i =0;i<Q;i++) {
		cout << rans[i] << "\n";
	}
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 134916 KB Output is correct
2 Correct 1178 ms 134956 KB Output is correct
3 Correct 1167 ms 134988 KB Output is correct
4 Correct 1183 ms 135000 KB Output is correct
5 Correct 1254 ms 134984 KB Output is correct
6 Correct 1210 ms 134944 KB Output is correct
7 Correct 1159 ms 135140 KB Output is correct
8 Correct 1118 ms 134948 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 10272 KB Output is correct
2 Correct 105 ms 10180 KB Output is correct
3 Correct 104 ms 10164 KB Output is correct
4 Correct 102 ms 10176 KB Output is correct
5 Correct 107 ms 10180 KB Output is correct
6 Correct 119 ms 10252 KB Output is correct
7 Correct 93 ms 7680 KB Output is correct
8 Correct 93 ms 8672 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 134916 KB Output is correct
2 Correct 1178 ms 134956 KB Output is correct
3 Correct 1167 ms 134988 KB Output is correct
4 Correct 1183 ms 135000 KB Output is correct
5 Correct 1254 ms 134984 KB Output is correct
6 Correct 1210 ms 134944 KB Output is correct
7 Correct 1159 ms 135140 KB Output is correct
8 Correct 1118 ms 134948 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct
11 Correct 110 ms 10272 KB Output is correct
12 Correct 105 ms 10180 KB Output is correct
13 Correct 104 ms 10164 KB Output is correct
14 Correct 102 ms 10176 KB Output is correct
15 Correct 107 ms 10180 KB Output is correct
16 Correct 119 ms 10252 KB Output is correct
17 Correct 93 ms 7680 KB Output is correct
18 Correct 93 ms 8672 KB Output is correct
19 Correct 1298 ms 139184 KB Output is correct
20 Correct 1288 ms 139148 KB Output is correct
21 Correct 1325 ms 139188 KB Output is correct
22 Correct 1270 ms 139160 KB Output is correct
23 Correct 1299 ms 139136 KB Output is correct
24 Correct 1257 ms 139232 KB Output is correct