oj.uz

Submission #79599

# Submission time Handle Problem Language Result Execution time Memory
79599 2018-10-15T05:17:12 Z ToMoClone Park (BOI16_park) C++17
100 / 100
 220 ms 32300 KB 
/*input
5 3 16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 2009;
int n, m, w, h, x[N], y[N], r[N], d[N], used[N], G[N][N];
pair<int, pair<int, int> > edge[3000005];

int dist(int a, int b) {
	int64_t val = 1ll * (x[a] - x[b]) * (x[a] - x[b]) + 1ll * (y[a] - y[b]) * (y[a] - y[b]);
	return (int)((sqrtl(val) + 1e-4));
}

int dijkstra(int S, int T) {
	memset(d, 127, sizeof d);
	memset(used, 0, sizeof used);

	d[S] = 0;
	for(int step = 1; step <= n + 4; ++ step) {
		int mxDist = INT_MAX, save = -1;
		for(int i = 1; i <= n + 4; ++ i)
			if(d[i] < mxDist && !used[i]) save = i, mxDist = d[i];

		used[save] = 1;
		for(int i = 1; i <= n + 4; ++ i)
			d[i] = min(d[i], max(d[save], G[save][i]));
	}
	return d[T];
}

int main(){
	scanf("%d%d%d%d", &n, &m, &w, &h);
	for(int i = 1; i <= n; ++ i) scanf("%d%d%d", &x[i], &y[i], &r[i]);

	memset(G, 127, sizeof G);
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= n; ++ j)
			G[i][j] = (dist(i, j) - r[i] - r[j]) / 2;

	for(int i = 1; i <= n; ++ i) {
		G[i][n + 3] = G[n + 3][i] = (w - x[i] - r[i]) / 2;
		G[i][n + 4] = G[n + 4][i] = (h - y[i] - r[i]) / 2;
		G[i][n + 1] = G[n + 1][i] = (x[i] - r[i]) / 2;
		G[i][n + 2] = G[n + 2][i] = (y[i] - r[i]) / 2;
	}
	
	vector<vector<int> > Ans(5, vector<int>(5));
	int A = dijkstra(n + 1, n + 2);
	int B = dijkstra(n + 1, n + 3);
	int C = dijkstra(n + 1, n + 4);
	int D = dijkstra(n + 2, n + 3);
	int E = dijkstra(n + 2, n + 4);
	int F = dijkstra(n + 3, n + 4);
	Ans[1][2] = Ans[2][1] = min({A, D, E});
	Ans[1][3] = Ans[3][1] = min({A, B, E, F});
	Ans[1][4] = Ans[4][1] = min({A, B, C});
	Ans[2][3] = Ans[3][2] = min({B, D, F});
	Ans[2][4] = Ans[4][2] = min({B, C, D, E});
	Ans[3][4] = Ans[4][3] = min({C, E, F});
	// for(int i = 1; i < 5; ++ i)
	// 	for(int j = 1; j < 5; ++ j) cout << i << ' ' << j << ' ' << Ans[i][j] << endl;
	// cout << dijkstra(n + 2, n + 3) << endl;

	while(m --) {
		int entrance, rad; scanf("%d%d", &rad, &entrance);
		for(int i = 1; i < 5; ++ i) if(Ans[entrance][i] >= rad || i == entrance) putchar(i + '0');
			putchar('\n');
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m, &w, &h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:43:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; ++ i) scanf("%d%d%d", &x[i], &y[i], &r[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:75:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int entrance, rad; scanf("%d%d", &rad, &entrance);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 16248 KB Output is correct
2 Correct 173 ms 16428 KB Output is correct
3 Correct 154 ms 16480 KB Output is correct
4 Correct 153 ms 16572 KB Output is correct
5 Correct 154 ms 16644 KB Output is correct
6 Correct 158 ms 16816 KB Output is correct
7 Correct 134 ms 16864 KB Output is correct
8 Correct 133 ms 16940 KB Output is correct
9 Correct 15 ms 16940 KB Output is correct
10 Correct 15 ms 16940 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 18276 KB Output is correct
2 Correct 61 ms 19444 KB Output is correct
3 Correct 46 ms 20368 KB Output is correct
4 Correct 46 ms 21372 KB Output is correct
5 Correct 62 ms 22508 KB Output is correct
6 Correct 47 ms 23684 KB Output is correct
7 Correct 62 ms 24732 KB Output is correct
8 Correct 50 ms 25952 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 16248 KB Output is correct
2 Correct 173 ms 16428 KB Output is correct
3 Correct 154 ms 16480 KB Output is correct
4 Correct 153 ms 16572 KB Output is correct
5 Correct 154 ms 16644 KB Output is correct
6 Correct 158 ms 16816 KB Output is correct
7 Correct 134 ms 16864 KB Output is correct
8 Correct 133 ms 16940 KB Output is correct
9 Correct 15 ms 16940 KB Output is correct
10 Correct 15 ms 16940 KB Output is correct
11 Correct 55 ms 18276 KB Output is correct
12 Correct 61 ms 19444 KB Output is correct
13 Correct 46 ms 20368 KB Output is correct
14 Correct 46 ms 21372 KB Output is correct
15 Correct 62 ms 22508 KB Output is correct
16 Correct 47 ms 23684 KB Output is correct
17 Correct 62 ms 24732 KB Output is correct
18 Correct 50 ms 25952 KB Output is correct
19 Correct 199 ms 27152 KB Output is correct
20 Correct 201 ms 28056 KB Output is correct
21 Correct 183 ms 29084 KB Output is correct
22 Correct 220 ms 30120 KB Output is correct
23 Correct 189 ms 31132 KB Output is correct
24 Correct 160 ms 32300 KB Output is correct