oj.uz

Submission #257427

# Submission time Handle Problem Language Result Execution time Memory
257427 2020-08-04T09:09:43 Z vioalbert Park (BOI16_park) C++14
100 / 100
 428 ms 50092 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 2e3+20;
int n, m;
ll w, h;
ll x[N], y[N], r[N];
struct edge {
	ll u, v, w;
	bool operator<(const edge& ot) {
		return w < ot.w;
	}
};
ll c[5][5], ans[5][5];
vector<edge> edges;

void read() {
	cin >> n >> m >> w >> h;
	for(int i = 1; i <= n; i++)
		cin >> x[i] >> y[i] >> r[i];
}

ll costToCircle(int i, int j) {
	ll xx = (x[i] - x[j]), yy = (y[i] - y[j]);
	return (ll)sqrt(xx * xx + yy * yy) - r[i] - r[j];
}

ll costToWall(int i, int j) {
	if(j == 1) {	//down
		return y[i] - r[i];
	} else if(j == 2) {	//right
		return w - x[i] - r[i];
	} else if(j == 3) {	//up
		return h - y[i] - r[i];
	} else if(j == 4) {	//left
		return x[i] - r[i];
	}
}

int par[N];

int find(int u) {
	if(u == par[u]) return u;
	else return par[u] = find(par[u]);
}

void join(int u, int v) {
	int parU = find(u), parV = find(v);
	par[parU] = parV;
}

void solve() {
	for(int i = 1; i <= n; i++) {
		for(int j = i+1; j <= n; j++) {
			ll cost = costToCircle(i, j);
			edges.push_back({i, j, cost});
		}
		for(int j = 1; j <= 4; j++) {
			ll cost = costToWall(i, j);
			edges.push_back({i, j+n, cost});
		}
	}
	sort(edges.begin(), edges.end());

	for(int i = 1; i <= n+4; i++)
		par[i] = i;
	for(int i = 1; i <= 4; i++) {
		for(int j = i+1; j <= 4; j++)
			c[i][j] = -1;
	}

	for(edge e : edges) {
		if(find(e.u) != find(e.v)) {
			join(e.u, e.v);
		}
		for(int i = 1; i <= 4; i++) {
			for(int j = i+1; j <= 4; j++) {
				if(find(i+n) == find(j+n) && c[i][j] == -1)
					c[i][j] = e.w;
			}
		}
	}

	ans[1][2] = ans[2][1] = min({c[1][4], c[1][3], c[1][2]});
	ans[1][3] = ans[3][1] = min({c[1][4], c[1][3], c[2][4], c[2][3]});
	ans[1][4] = ans[4][1] = min({c[1][4], c[2][4], c[3][4]});
	ans[2][3] = ans[3][2] = min({c[1][2], c[2][4], c[2][3]});
	ans[2][4] = ans[4][2] = min({c[1][2], c[1][3], c[2][4], c[3][4]});
	ans[3][4] = ans[4][3] = min({c[2][3], c[1][3], c[3][4]});

	while(m--) {
		ll k; int e; cin >> k >> e;
		for(int i = 1; i <= 4; i++) {
			if(e == i || k * 2 <= ans[e][i])
				cout << i;
		}
		cout << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}

Compilation message

park.cpp: In function 'll costToWall(int, int)':
park.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 49732 KB Output is correct
2 Correct 415 ms 49732 KB Output is correct
3 Correct 428 ms 49708 KB Output is correct
4 Correct 404 ms 49860 KB Output is correct
5 Correct 395 ms 49832 KB Output is correct
6 Correct 377 ms 49836 KB Output is correct
7 Correct 319 ms 49988 KB Output is correct
8 Correct 334 ms 49840 KB Output is correct
9 Correct 1 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 47 ms 1388 KB Output is correct
2 Correct 42 ms 2416 KB Output is correct
3 Correct 48 ms 2288 KB Output is correct
4 Correct 56 ms 2416 KB Output is correct
5 Correct 49 ms 2416 KB Output is correct
6 Correct 71 ms 2416 KB Output is correct
7 Correct 36 ms 1792 KB Output is correct
8 Correct 37 ms 1784 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 49732 KB Output is correct
2 Correct 415 ms 49732 KB Output is correct
3 Correct 428 ms 49708 KB Output is correct
4 Correct 404 ms 49860 KB Output is correct
5 Correct 395 ms 49832 KB Output is correct
6 Correct 377 ms 49836 KB Output is correct
7 Correct 319 ms 49988 KB Output is correct
8 Correct 334 ms 49840 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 47 ms 1388 KB Output is correct
12 Correct 42 ms 2416 KB Output is correct
13 Correct 48 ms 2288 KB Output is correct
14 Correct 56 ms 2416 KB Output is correct
15 Correct 49 ms 2416 KB Output is correct
16 Correct 71 ms 2416 KB Output is correct
17 Correct 36 ms 1792 KB Output is correct
18 Correct 37 ms 1784 KB Output is correct
19 Correct 420 ms 49988 KB Output is correct
20 Correct 422 ms 49988 KB Output is correct
21 Correct 425 ms 49964 KB Output is correct
22 Correct 421 ms 49964 KB Output is correct
23 Correct 421 ms 49964 KB Output is correct
24 Correct 375 ms 50092 KB Output is correct