QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547545#8236. Snake MoveChuggWA 263ms48224kbC++202.4kb2024-09-04 22:34:022024-09-04 22:34:02

Judging History

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

  • [2024-09-04 22:34:02]
  • 评测
  • 测评结果:WA
  • 用时:263ms
  • 内存:48224kb
  • [2024-09-04 22:34:02]
  • 提交

answer

#include <bits/stdc++.h>

constexpr int ds[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void solve() 
{
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::pair<int, int>> a(k);
    for (auto &[x, y] : a) {
        std::cin >> x >> y;
        x--, y--;
    }
    std::vector<std::string> s(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> s[i];
    } 
    int cnt = 1;
    std::vector ans(n, std::vector<int>(m));
    for (const auto &[x, y] : a) {
        ans[x][y] = -cnt;
        cnt++;
    }
    std::queue<std::pair<int, int>> q, tq;
    ans[a[0].first][a[0].second] = 1;
    q.emplace(a[0]);
    while (!q.empty() || !tq.empty()) {
        int x, y;
        if (!q.empty()) {
            if (!tq.empty()) {
                auto [t1, t2] = q.front();
                auto [t3, t4] = tq.front();
                if (ans[t1][t2] < ans[t3][t4]) {
                    x = t1;
                    y = t2;
                    q.pop();
                } else {
                    x = t3;
                    y = t4;
                    tq.pop();
                }
            } else {
                auto [tx, ty] = q.front();
                x = tx;
                y = ty;
                q.pop();
            }
        } else {
            auto [tx, ty] = tq.front();
            x = tx;
            y = ty;
            tq.pop();
        }
        for (int i = 0; i < 4; ++i) {
            int nx = x + ds[i][0];
            int ny = y + ds[i][1];
            if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
            if (s[nx][ny] == '#') continue;
            if (ans[nx][ny] == 0) {
                ans[nx][ny] = ans[x][y] + 1;
                q.emplace(nx, ny);
            }
            if (ans[nx][ny] < 0) {
                ans[nx][ny] = std::max(k + ans[nx][ny] + 2, ans[x][y] + 1);
                tq.emplace(nx, ny);
            }
        }
    }
    uint64_t sum = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (ans[i][j] > 0) ans[i][j]--;
            else ans[i][j] = 0;
            sum = sum + (uint64_t)ans[i][j] * (uint64_t)ans[i][j];
            // std::cout << ans[i][j] << " \n"[j == m - 1];
        }
    }
    std::cout << sum << '\n';
}

int main() 
{
    std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);
    
    int t = 1;
    while(t--) {
        solve();
    }
    
    return 0;
}

详细

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 166ms
memory: 47196kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 263ms
memory: 47156kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 15ms
memory: 48224kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 20ms
memory: 46684kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 185ms
memory: 47420kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803413398430

result:

wrong answer 1st lines differ - expected: '49803365625286', found: '49803413398430'