oj.uz

Submission #257415

# Submission time Handle Problem Language Result Execution time Memory
257415 2020-08-04T08:55:47 Z vioalbert Park (BOI16_park) C++14
0 / 100
 360 ms 33504 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 2e3+10;
int n, m;
ll w, h;
ll x[N], y[N], r[N];
struct edge {
	int u, v; ll w;
	edge() {};
	edge(int _u, int _v, ll _w) : u(_u), v(_v), w(_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(edge(i, j, cost));
		}
		for(int j = 1; j <= 4; j++) {
			ll cost = costToWall(i, j);
			edges.push_back(edge(i, j+n, cost));
		}
	}

	// for(edge e : edges) {
	// 	cerr << e.u-1 << ' ' << e.v-1 << ' ' << e.w << '\n';
	// }
	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)) {
			// cerr << e.u << ' ' << e.v << '\n';
			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] < 0) {
					// cerr << i << ' ' << j << ' ' << e.w << '\n';
					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[1][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]});

	// for(int i = 1; i <= 4; i++) {
	// 	for(int j = i+1; j <= 4; j++)
	// 		cerr << i << ' ' << j << "->" << ans[i][j] << '\n';
	// }

	while(m--) {
		ll k; int e; cin >> k >> e;
		for(int i = 1; i <= 4; i++) {
			if(e == i) cout << i;
			else if(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:42:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 33504 KB Output is correct
2 Correct 358 ms 33368 KB Output is correct
3 Correct 359 ms 33504 KB Output is correct
4 Incorrect 358 ms 33360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 33504 KB Output is correct
2 Correct 358 ms 33368 KB Output is correct
3 Correct 359 ms 33504 KB Output is correct
4 Incorrect 358 ms 33360 KB Output isn't correct
5 Halted 0 ms 0 KB -