oj.uz

Submission #437100

# Submission time Handle Problem Language Result Execution time Memory
437100 2021-06-25T19:28:32 Z penguinhacker Park (BOI16_park) C++14
100 / 100
 382 ms 29764 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2000, mxM=1e5;
int n, m, w, h, p[mxN+4];
vector<ar<int, 3>> edges;
ar<int, 3> visitors[mxM];
string ans[mxM];
bool vis[4], bad[4][4];

struct circ {
	int x, y, r;
} c[mxN];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

void dfs(int u) {
	vis[u]=1;
	for (int v=0; v<4; ++v)
		if (!vis[v]&&!bad[u][v])
			dfs(v);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> w >> h;
	for (int i=0; i<n; ++i)
		cin >> c[i].x >> c[i].y >> c[i].r;
	edges.reserve(4*n+n*(n-1)/2);
	for (int i=0; i<n; ++i) {
		for (int j=i+1; j<n; ++j) {
			ll x=c[i].x-c[j].x;
			ll y=c[i].y-c[j].y;
			ll d=sqrt(x*x+y*y)-1;
			while((d+1)*(d+1)<=x*x+y*y)
				++d;
			int d2=d-c[i].r-c[j].r;
			edges.push_back({d2, i+4, j+4});
		}
		edges.push_back({c[i].y-c[i].r, 0, i+4}); // down
		edges.push_back({w-c[i].x-c[i].r, 1, i+4}); // right
		edges.push_back({h-c[i].y-c[i].r, 2, i+4}); // up
		edges.push_back({c[i].x-c[i].r, 3, i+4}); // left
	}
	for (int i=0; i<m; ++i) {
		int r, t;
		cin >> r >> t, --t;
		visitors[i]={r, t, i};
	}
	sort(edges.rbegin(), edges.rend());
	sort(visitors, visitors+m);
	iota(p, p+n+4, 0);
	for (int i=0; i<m; ++i) {
		while(edges.size()&&edges.back()[0]<2*visitors[i][0]) {
			//cout << edges.back()[0] << " " << edges.back()[1] << " " << edges.back()[2] << endl;
			int u=find(edges.back()[1]), v=find(edges.back()[2]);
			//cout << i << " " << u << " " << v << endl;
			p[v]=u;
			edges.pop_back();
		}
		for (int j=0; j<4; ++j) {
			int nxt=(j+1)%4;
			if (find(j)==find(nxt))
				for (int k=2; k<=4; ++k)
					bad[nxt][(j+k)%4]=bad[(j+k)%4][nxt]=1;
			if (find(j)==find((j+2)%4))
				for (int k1 : {j, (j+3)%4})
					for (int k2 : {nxt, (j+2)%4})
						bad[k1][k2]=bad[k2][k1]=1;
		}
		memset(vis, 0, sizeof(vis));
		dfs(visitors[i][1]);
		for (int j=0; j<4; ++j)
			if (vis[j])
				ans[visitors[i][2]]+=(char)('1'+j);
	}
	for (int i=0; i<m; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 27204 KB Output is correct
2 Correct 335 ms 27132 KB Output is correct
3 Correct 329 ms 27168 KB Output is correct
4 Correct 324 ms 27204 KB Output is correct
5 Correct 330 ms 27076 KB Output is correct
6 Correct 331 ms 27144 KB Output is correct
7 Correct 351 ms 27076 KB Output is correct
8 Correct 307 ms 27084 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 3 ms 3468 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6216 KB Output is correct
2 Correct 56 ms 6172 KB Output is correct
3 Correct 56 ms 6124 KB Output is correct
4 Correct 60 ms 6232 KB Output is correct
5 Correct 57 ms 6240 KB Output is correct
6 Correct 56 ms 6300 KB Output is correct
7 Correct 54 ms 6080 KB Output is correct
8 Correct 55 ms 6044 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 27204 KB Output is correct
2 Correct 335 ms 27132 KB Output is correct
3 Correct 329 ms 27168 KB Output is correct
4 Correct 324 ms 27204 KB Output is correct
5 Correct 330 ms 27076 KB Output is correct
6 Correct 331 ms 27144 KB Output is correct
7 Correct 351 ms 27076 KB Output is correct
8 Correct 307 ms 27084 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 3 ms 3468 KB Output is correct
11 Correct 56 ms 6216 KB Output is correct
12 Correct 56 ms 6172 KB Output is correct
13 Correct 56 ms 6124 KB Output is correct
14 Correct 60 ms 6232 KB Output is correct
15 Correct 57 ms 6240 KB Output is correct
16 Correct 56 ms 6300 KB Output is correct
17 Correct 54 ms 6080 KB Output is correct
18 Correct 55 ms 6044 KB Output is correct
19 Correct 382 ms 29500 KB Output is correct
20 Correct 375 ms 29508 KB Output is correct
21 Correct 378 ms 29708 KB Output is correct
22 Correct 381 ms 29496 KB Output is correct
23 Correct 377 ms 29496 KB Output is correct
24 Correct 375 ms 29764 KB Output is correct