oj.uz

Submission #350888

# Submission time Handle Problem Language Result Execution time Memory
350888 2021-01-19T09:38:02 Z saniyar_krmi Park (BOI16_park) C++14
58 / 100
 902 ms 262148 KB 
// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#pragma GCC optimize ("Ofast")
 
#define F first
#define S second
//#define mul(x, y) (((x) * (y)) %mod)
//#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
 
const int maxn = 5e6 + 10;
 
int n, m, w, h;
vector <pair<ld, pii>> all;
ld tx[maxn], ty[maxn], tr[maxn];
 
int p[maxn], sz[maxn];
 
string ans[maxn];
 
int get(int a){
	return p[a] = (p[a] == a ? a : get(p[a]));
}
 
bool same(int a, int b){
	return get(a) == get(b);
}
 
void unite(int a, int b){
	a = get(a), b = get(b);
	if(a == b)
		return;
	if(sz[a] < sz[b])
		swap(a, b);
	p[b] = a, sz[a] += sz[b];
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
 
	for(int i=0; i<maxn; i++) p[i] = i, sz[i] = 1;
 
	cin >> n >> m >> w >> h;
	for(int i=0; i<n; i++){
		cin >> tx[i] >> ty[i] >> tr[i];
		for(int j=0; j<i; j++){
			ld d = hypot(abs(tx[i] - tx[j]), abs(ty[i] - ty[j])) - tr[i] - tr[j];
			all.push_back({d, {i, j}});
		}
		all.push_back({ty[i] - tr[i], {i, n+1}});
		all.push_back({tx[i] - tr[i], {i, n+2}});
		all.push_back({w - tx[i] - tr[i], {i, n+3}});
		all.push_back({h - ty[i] - tr[i], {i, n+4}});
	}
 
	ld r;
	int e;
	for(int i=1; i<=m; i++){
		cin >> r >> e;
		all.push_back({r*2, {-i, e}});
	}
	sort(all.begin(), all.end());
 
	for(auto a: all){
		if(a.S.F < 0){
			int j = -(a.S.F + 1);
			int e = a.S.S;
			if(same(n + 1, n + 4) && same(n + 2, n + 3)){
				ans[j] = char('0' + e);
			}
			else if(same(n + 1, n + 4)){
				if(e == 1 || e == 4){
					if(!same(n + 1, n + 2) && !same(n + 2, n + 4))
						ans[j] = "14";
					else
						ans[j] = char('0' + e);
				}
				else{
					if(!same(n + 1, n + 3) && !same(n + 3, n + 4))
						ans[j] = "23";
					else
						ans[j] = char('0' + e);
				}
			}
			else if(same(n + 2, n + 3)){
				if(e == 1 || e == 2){
					if(!same(n + 1, n + 2) && !same(n + 1, n + 3))
						ans[j] = "12";
					else
						ans[j] = char('0' + e);
				}
				else{
					if(!same(n + 2, n + 4) && !same(n + 3, n + 4))
						ans[j] = "34";
					else
						ans[j] = char('0' + e);
				}
			}
			else{
				vector <int> ok(5, 1);
				if(same(n + 1, n + 2)) ok[1] = 0;
				if(same(n + 1, n + 3)) ok[2] = 0;
				if(same(n + 3, n + 4)) ok[3] = 0;
				if(same(n + 2, n + 4)) ok[4] = 0;
 
				for(int k=1; k<=4; k++)
					if((ok[e] && ok[k]) || e == k)
						ans[j] += char('0' + k);
			}
		}
		else{
			unite(a.S.F, a.S.S);
		}
	}
 
	for(int i=0; i<m; i++)
		cout << ans[i] << '\n';
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 261912 KB Output is correct
2 Correct 880 ms 262072 KB Output is correct
3 Correct 888 ms 262088 KB Output is correct
4 Correct 902 ms 262144 KB Output is correct
5 Correct 884 ms 262120 KB Output is correct
6 Correct 873 ms 261912 KB Output is correct
7 Correct 761 ms 261944 KB Output is correct
8 Correct 759 ms 262032 KB Output is correct
9 Correct 139 ms 196076 KB Output is correct
10 Correct 132 ms 196076 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 200412 KB Output is correct
2 Correct 219 ms 200540 KB Output is correct
3 Correct 208 ms 200292 KB Output is correct
4 Correct 216 ms 200292 KB Output is correct
5 Correct 234 ms 200472 KB Output is correct
6 Correct 244 ms 200412 KB Output is correct
7 Correct 207 ms 200292 KB Output is correct
8 Correct 203 ms 200420 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 261912 KB Output is correct
2 Correct 880 ms 262072 KB Output is correct
3 Correct 888 ms 262088 KB Output is correct
4 Correct 902 ms 262144 KB Output is correct
5 Correct 884 ms 262120 KB Output is correct
6 Correct 873 ms 261912 KB Output is correct
7 Correct 761 ms 261944 KB Output is correct
8 Correct 759 ms 262032 KB Output is correct
9 Correct 139 ms 196076 KB Output is correct
10 Correct 132 ms 196076 KB Output is correct
11 Correct 218 ms 200412 KB Output is correct
12 Correct 219 ms 200540 KB Output is correct
13 Correct 208 ms 200292 KB Output is correct
14 Correct 216 ms 200292 KB Output is correct
15 Correct 234 ms 200472 KB Output is correct
16 Correct 244 ms 200412 KB Output is correct
17 Correct 207 ms 200292 KB Output is correct
18 Correct 203 ms 200420 KB Output is correct
19 Runtime error 485 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -