QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325082#8236. Snake Moveucup-team2000#WA 1037ms224040kbC++202.7kb2024-02-11 04:07:022024-02-11 04:07:03

Judging History

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

  • [2024-02-11 04:07:03]
  • 评测
  • 测评结果:WA
  • 用时:1037ms
  • 内存:224040kb
  • [2024-02-11 04:07:02]
  • 提交

answer

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

#define int long long
typedef pair<int, int> pi;
#define f first
#define s second
#define lep(i,a,b) for(int i=(a); i <= (b); i++)
#define pb push_back

const int maxn = 3000, maxk = 100005, inf = 1e18;
int n, m, k;
pi snake[maxk];
pair<char, int> grid[maxn][maxn];
bool vis[maxn][maxn];
unsigned long long ans[maxn][maxn];
pi dirs[] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

bool isValid(pi x) {
    return x.f >= 0 && x.f <= n + 1 && x.s >= 0 && x.s <= m + 1;
}

int dis(pi x, pi y) {
    return abs(x.f - y.f) + abs(x.s - y.s);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;

    for (int i = 0; i < k; ++i) {
        cin >> snake[i].f >> snake[i].s;
        // snake[i].f--; snake[i].s--;
    }

    for (int i = 0; i <= n + 1; ++i) grid[0][i] = grid[n + 1][i] = {'#', inf};
    for (int i = 0; i <= m + 1; ++i) grid[i][0] = grid[i][m + 1] = {'#', inf};

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) { 
            cin >> grid[i][j].f;
            grid[i][j].s = inf;
        }
    }
    for (int i = 0; i < k; ++i)
        grid[snake[i].f][snake[i].s] = {'$', k - i};
    
    for (int i = 0; i <= n + 1; ++i) {
        for (int j = 0; j <= m + 1; ++j) {
            if (grid[i][j].f == '#') {
                vis[i][j] = true;
                ans[i][j] = inf;
            }
        }
    }

    priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
    pq.push({0, snake[0]});
    vis[snake[0].f][snake[0].s] = true;
    while (!pq.empty()) {
        pair<int, pi> tp = pq.top(); pq.pop();
        int weight = tp.f;
        pi place = tp.s;
        ans[place.f][place.s] = weight;
        for (auto dir : dirs) {
            int dx = dir.f, dy = dir.s;
            pi new_place = {place.f + dx, place.s + dy};
            if (isValid(new_place) && !vis[new_place.f][new_place.s]) {
                vis[new_place.f][new_place.s] = true;
                int new_weight;
                if (grid[new_place.f][new_place.s].f != '.') {
                    new_weight = max(weight + 1, grid[new_place.f][new_place.s].s);
                } else {
                    new_weight = weight + 1;
                }
                pq.push({new_weight, new_place});
            }
        }
    }
    unsigned long long res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (ans[i][j] != inf) {
                unsigned long long mod_ans = (ans[i][j] * ans[i][j]);
                res = (res + mod_ans); 
            }
        }
    }
    cout << res;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11772kb

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

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

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Wrong Answer
time: 1037ms
memory: 224040kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

7529339761928584953

result:

wrong answer 1st lines differ - expected: '35141960580077', found: '7529339761928584953'