QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#637133#8236. Snake MovefoolnineTL 0ms3780kbC++201.9kb2024-10-13 09:55:172024-10-13 09:55:17

Judging History

你现在查看的是最新测评结果

  • [2024-10-13 09:55:17]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3780kb
  • [2024-10-13 09:55:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
const int inf = 1e9 + 7;
const int dx[4] = { 0,0,1,-1 };
const int dy[4] = { 1,-1,0,0 };

struct node {
    int x, y, d;

    bool operator < (const node &y) const {
        return x < y.x;
    }
    bool operator > (const node &y) const {
        return x > y.x;
    }
};

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    priority_queue<node, vector<node>, greater<node>> pq;

    vector<vector<int>> tim(n, vector<int>(m, 1));
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;

        tim[x][y] = k - i;
        if (i == 0) {
            tim[x][y] = 0;
            pq.emplace(x, y, 0);
        }
    }

    vector<vector<int>> G(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            G[i][j] = (s[j] == '.' ? 0 : 1);
        }
    }

    vector<vector<int>> dis(n, vector<int>(m, inf));

    while (!pq.empty()) {
        auto [x, y, d] = pq.top();
        pq.pop();

        if (d >= dis[x][y]) {
            continue;
        }

        dis[x][y] = d;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m || G[nx][ny] == 1) {
                continue;
            }

            pq.emplace(nx, ny, max(d + 1, tim[nx][ny]));
        }
    }

    u64 ans = 0;
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            if (dis[x][y] == inf || dis[x][y] == 0) {
                continue;
            }
            u64 t = dis[x][y];
            ans += t * t;
        }
    }
    cout << ans << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

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: 3780kb

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: 3504kb

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
........................................................................................................#................................................................................................................................................................#................

output:


result: