QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#324457 | #8236. Snake Move | ucup-team484# | TL | 0ms | 3608kb | C++17 | 1.5kb | 2024-02-10 19:39:57 | 2024-02-10 19:39:57 |
Judging History
answer
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef unsigned long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
vector<pair<int, int>> a(k);
vector<vector<int>> ans(n, vector<int>(m, mod)), vis(n, vector<int>(m, 0));
for (int i = 0; i < k; i++) {
cin >> a[i].first >> a[i].second;
a[i].first--;
a[i].second--;
vis[a[i].first][a[i].second] = i;
}
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0; j < m; j++)
if (s[j] == '#')
vis[i][j] = -1;
}
ans[a[0].first][a[0].second] = 0;
priority_queue<pair<int, pair<int, int>>> q;
auto upd = [&](auto p, int d) {
for (int i = 0; i < 4; i++) {
int nx = p.first + dx[i];
int ny = p.second + dy[i];
if (nx < 0 || ny < 0 || n <= nx || m <= ny || vis[nx][ny] == -1)
continue;
if ((vis[nx][ny] + d + 1 >= k || vis[nx][ny] == 0) && ans[nx][ny] > d + 1) {
ans[nx][ny] = d + 1;
q.push(make_pair(d + 1, make_pair(nx, ny)));
}
}
};
for (int i = 0; i < k; i++)
q.push(make_pair(i, a[0]));
while (!q.empty()) {
auto [d, p] = q.top();
q.pop();
upd(p, d);
}
ll res = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (ans[i][j] != mod)
res += (ll)ans[i][j] * (ll)ans[i][j];
cout << res << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: -100
Time Limit Exceeded
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................