oj.uz

Submission #389866

# Submission time Handle Problem Language Result Execution time Memory
389866 2021-04-14T18:02:56 Z saleh Park (BOI16_park) C++17
0 / 100
 637 ms 35960 KB 
#include <bits/stdc++.h>

#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2000 + 123, MAXM = 100 * 1000 + 123;














int n, m, w, h, x[MAXN], y[MAXN], r[MAXN], a[MAXM], R[MAXM], e[MAXM], g[MAXN][MAXN], par[MAXN];
deque<pii> v;
vector<int> ans[MAXM];
bitset<3 + 1 + 3 + 3> mark[1 + 3 + 3 + 3];

int dis(int z, int w) { return sqrt(1. * abs(x[z] - x[w]) * abs(x[z] - x[w]) + 1. * abs(y[z] - y[w]) * abs(y[z] - y[w])); }

int gp(int z) { return ~par[z]? par[z] = gp(par[z]): z; }
void mrg(int z, int w) {
	z = gp(z);
	w = gp(w);
	if (z != w) par[z] = w;
}
void cut(int z) { mark[z][1] = mark[z][3] = mark[z][4] = mark[z][2] = mark[1][z] = mark[3][z] = mark[4][z] = mark[2][z] = true; mark[z][z] = false; }


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	memset(par, -1, sizeof par);
	cin >> n >> m >> w >> h;
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> r[i];
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
		g[i][j] = g[j][i] = dis(i, j) - r[i] - r[j];
		v.push_back({i, j});
	}
	for (int i = 0; i < n; i++) {
		v.push_back({n, i});
		v.push_back({n + 1, i});
		v.push_back({n + 2, i});
		v.push_back({n + 3, i});
		g[n][i] = g[i][n] = y[i] - r[i];
		g[n + 1][i] = g[i][n + 1] = w - x[i] - r[i];
		g[n + 2][i] = g[i][n + 2] = h - y[i] - r[i];
		g[n + 3][i] = g[i][n + 3] = x[i] - r[i];
	}
	sort(v.begin(), v.end(), [](pii z, pii w) { return g[z.ft][z.sd] < g[w.ft][w.sd]; });
	for (int i = 0; i < m; i++) cin >> R[i] >> e[i];
	iota(a, a + m, 0);
	sort(a, a + m, [](int z, int w) { return R[z] < R[w]; });
	for (int i = 0; i < m; i++) {
		int j = a[i];
		while (!v.empty() && g[v.front().ft][v.front().sd] < (R[j] << 1)) {
			mrg(v.front().ft, v.front().sd);
			v.pop_front();
		}
		if (gp(n) == gp(n + 1)) cut(2);
		if (gp(n + 1) == gp(n + 2)) cut(3);
		if (gp(n + 2) == gp(n + 3)) cut(4);
		if (gp(n + 3) == gp(n)) cut(1);
		if (gp(n) == gp(n + 2)) mark[1][2] = mark[1][3] = mark[4][2] = mark[4][3] = mark[2][1] = mark[3][1] = mark[2][4] = mark[3][4] = true;
		if (gp(n + 1) == gp(n + 3)) mark[1][4] = mark[1][3] = mark[2][4] = mark[2][3] = mark[4][1] = mark[3][1] = mark[4][2] = mark[3][2] = true;
		for (int k = 1; k <= 4; k++) if (!mark[e[j]][k]) ans[j].push_back(k);
	}
	for (int i = 0; i < m; i++) {
		for (auto j : ans[i]) cout << j;
		cout << '\n';
	}
	return 0;
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 35804 KB Output is correct
2 Correct 602 ms 35704 KB Output is correct
3 Correct 637 ms 35864 KB Output is correct
4 Correct 616 ms 35960 KB Output is correct
5 Correct 611 ms 35868 KB Output is correct
6 Correct 613 ms 35860 KB Output is correct
7 Correct 468 ms 35940 KB Output is correct
8 Correct 442 ms 35860 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Incorrect 2 ms 2636 KB Output isn't correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8576 KB Output is correct
2 Correct 75 ms 9288 KB Output is correct
3 Correct 83 ms 9284 KB Output is correct
4 Correct 77 ms 9288 KB Output is correct
5 Correct 79 ms 9284 KB Output is correct
6 Correct 80 ms 9284 KB Output is correct
7 Incorrect 68 ms 8100 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 35804 KB Output is correct
2 Correct 602 ms 35704 KB Output is correct
3 Correct 637 ms 35864 KB Output is correct
4 Correct 616 ms 35960 KB Output is correct
5 Correct 611 ms 35868 KB Output is correct
6 Correct 613 ms 35860 KB Output is correct
7 Correct 468 ms 35940 KB Output is correct
8 Correct 442 ms 35860 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Incorrect 2 ms 2636 KB Output isn't correct