QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#585151#8236. Snake MoveFiatiustitiaWA 457ms119200kbC++202.4kb2024-09-23 19:24:052024-09-23 19:24:06

Judging History

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

  • [2024-09-23 19:24:06]
  • 评测
  • 测评结果:WA
  • 用时:457ms
  • 内存:119200kb
  • [2024-09-23 19:24:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    const int INF = 1e9;
    vector dis(n, vector<int>(m, INF));
    vector to_back(n, vector<int>(m, 0)), vis(n, vector<int>(m, 0));
    vector<string> g(n);
    auto check = [&](int x, int y)
    {
        return x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#';
    };
    using P = pair<int, int>;
    vector<P> snake(k);
    for (int i = 0; i < k; i++)
    {
        auto &[x, y] = snake[i];
        cin >> x >> y;
        x--, y--;
        to_back[x][y] = k - 1 - i;
    }
    using T = array<int, 3>;
    priority_queue<T> p;
    queue<T> q;
    for (auto &s : g)
        cin >> s;

    q.push(T({0,snake[0].first, snake[0].second}));
    dis[snake[0].first][snake[0].second] = 0;
    while (!q.empty())
    {
        auto [ta, xa, ya] = q.front();
        int x = xa,y = ya,t = ta;
        if (!p.empty())
        {
            auto [tb,xb,yb] = p.top();
            tb = -tb;
            if (tb < ta)
            {
                x = xb,y = yb,t = tb;
                p.pop();
            }
            else
            {
                q.pop();
            }
        }
        else
            q.pop();
        if (vis[x][y])
            continue;
        vis[x][y] = 1;
        for (int i = 0; i < 4; i++)
        {
            auto [nx, ny] = P(x + dir[i][0], y + dir[i][1]);
            if (!check(nx, ny) || vis[nx][ny])
                continue;
            if (to_back[nx][ny])
            {
                dis[nx][ny] = min(dis[nx][ny], t + 1 + max(0,to_back[nx][ny] - dis[x][y]));
                p.push(T({-dis[nx][ny],nx,ny}));
            }
            else
            {
                dis[nx][ny] = min(dis[nx][ny], t + 1);
                q.push(T({dis[nx][ny], nx, ny}));
            }
        }
    }
    uint64_t res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (dis[i][j] == INF)
                continue;
            res += 1ull * dis[i][j] * dis[i][j];
        }
    cout << res << '\n';
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    auto t = clock();
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
#ifdef LOCAL
    cerr << clock() - t << '\n';
#endif
    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: 3596kb

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 416ms
memory: 115448kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 457ms
memory: 115456kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 16ms
memory: 118864kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 24ms
memory: 114688kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 410ms
memory: 115624kb

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:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: 0
Accepted
time: 438ms
memory: 119200kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749285

result:

ok single line: '22509095749285'

Test #10:

score: 0
Accepted
time: 16ms
memory: 114756kb

input:

3000 2900 10
326 1781
325 1781
325 1782
325 1783
325 1784
324 1784
324 1783
323 1783
323 1782
324 1782
##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...

output:

40571

result:

ok single line: '40571'

Test #11:

score: -100
Wrong Answer
time: 19ms
memory: 114952kb

input:

2900 3000 10
2447 135
2447 136
2447 137
2447 138
2447 139
2447 140
2448 140
2448 139
2449 139
2449 138
.#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...

output:

251

result:

wrong answer 1st lines differ - expected: '2705', found: '251'