Submission #28621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28621	2017-07-16T08:05:48 Z	Official Fan of ACG(#1221, cseteram, 16silver, pps789)	Oriental P.A.D.A.K (FXCUP2_padak)	C++14	1 / 1	993 ms	65072 KB

padak

#include <cstdio>
#include <queue>
#include <map>
#include <deque>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, -1, 0, 1 };

int n, m, k, b, z;
vector<vector<int>> arr;
queue<pii> que;
deque<int> deq, deq2;

void bfs()
{
	while (!que.empty()) {
		int r, c;
		tie(r, c) = que.front();
		que.pop();

		for (int k = 0; k < 4; k++) {
			int nr = r + dy[k], nc = c + dx[k];
			if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
			if (arr[nr][nc]) continue;
			que.push({ nr, nc });
			arr[nr][nc] = arr[r][c] + 1;
			deq.push_back(arr[nr][nc]);
			deq2.push_back(arr[nr][nc]);
		}
	}
}

int main()
{
	scanf("%d%d%d%d%d", &n, &m, &k, &b, &z);
	arr.resize(n, vector<int>(m));
	for (int i = 0; i < k; i++) {
		int r, c;
		scanf("%d%d", &r, &c);
		--r, --c;
		que.push({ r, c });
		arr[r][c] = 1;
	}
	if (z == 0) {
		printf("0 0");
		return 0;
	}
	if (k == 0) {
		printf("%d %d", n * m, n * m);
		return 0;
	}

	bfs();

	int scnt = 0, lcnt = 0, t;

	t = 2;
	while (!deq.empty()) {
		for (int i = 0; i < z; i++) {
			if (deq.empty()) break;
			deq.pop_front();
			lcnt++;
		}
		while (!deq.empty() && deq.front() <= t)
			deq.pop_front();
		++t;
	}

	t = 2;
	while (!deq2.empty()) {
		for (int i = 0; i < z; i++) {
			if (deq2.empty()) break;
			deq2.pop_back();
			scnt++;
		}
		while (!deq2.empty() && deq2.front() <= t)
			deq2.pop_front();
		++t;
	}

	printf("%d %d", scnt, lcnt);	
	return 0;
}

Compilation message

padak.cpp: In function 'int main()':
padak.cpp:37:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &n, &m, &k, &b, &z);
                                         ^
padak.cpp:41:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &r, &c);
                        ^

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1940 KB	Output is correct
2	Correct	0 ms	1940 KB	Output is correct
3	Correct	46 ms	14340 KB	Output is correct
4	Correct	36 ms	14280 KB	Output is correct
5	Correct	46 ms	14304 KB	Output is correct
6	Correct	46 ms	17364 KB	Output is correct
7	Correct	46 ms	14240 KB	Output is correct
8	Correct	36 ms	14240 KB	Output is correct
9	Correct	99 ms	65072 KB	Output is correct
10	Correct	49 ms	14312 KB	Output is correct
11	Correct	66 ms	14252 KB	Output is correct
12	Correct	49 ms	14300 KB	Output is correct
13	Correct	43 ms	17372 KB	Output is correct
14	Correct	46 ms	14252 KB	Output is correct
15	Correct	39 ms	14240 KB	Output is correct
16	Correct	146 ms	65020 KB	Output is correct
17	Correct	106 ms	14332 KB	Output is correct
18	Correct	103 ms	14216 KB	Output is correct
19	Correct	86 ms	14304 KB	Output is correct
20	Correct	56 ms	17340 KB	Output is correct
21	Correct	106 ms	14236 KB	Output is correct
22	Correct	39 ms	14244 KB	Output is correct
23	Correct	193 ms	64980 KB	Output is correct
24	Correct	483 ms	14284 KB	Output is correct
25	Correct	423 ms	14232 KB	Output is correct
26	Correct	436 ms	14252 KB	Output is correct
27	Correct	623 ms	17328 KB	Output is correct
28	Correct	429 ms	14204 KB	Output is correct
29	Correct	423 ms	14108 KB	Output is correct
30	Correct	993 ms	64984 KB	Output is correct
31	Correct	43 ms	14340 KB	Output is correct
32	Correct	116 ms	65072 KB	Output is correct