# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28621 | Official Fan of ACG (#68) | Oriental P.A.D.A.K (FXCUP2_padak) | C++14 | 993 ms | 65072 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |