Submission #79599

#	Time	Username	Problem	Language	Result	Execution time	Memory
79599		ToMoClone	Park (BOI16_park)	C++17	100 / 100	220 ms	32300 KiB

park

/*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 (stderr)

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42