QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#712960#8236. Snake MoveKafuuChinocpp#WA 281ms379948kbC++143.4kb2024-11-05 17:38:102024-11-05 17:38:11

Judging History

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

  • [2024-11-05 17:38:11]
  • 评测
  • 测评结果:WA
  • 用时:281ms
  • 内存:379948kb
  • [2024-11-05 17:38:10]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int max1 = 3000, max2 = 1e5;
const int inf = 0x3f3f3f3f;

int n, m, k;
int num[max1 + 5][max1 + 5];
char Map[max1 + 5][max1 + 5];
int f[max1 + 5][max1 + 5], g[max1 + 5][max1 + 5];

struct Point
{
    int x, y;
    Point () {}
    Point ( int __x, int __y )
        { x = __x, y = __y; }
};

vector <Point> bin[max1 * max1 + max2];

int main ()
{
    int x, y, startx, starty;
    scanf("%d%d%d", &n, &m, &k);
    for ( int i = 1; i <= k; i ++ )
    {
        scanf("%d%d", &x, &y);
        num[x][y] = i;
        if ( i == 1 )
            startx = x, starty = y;
    }

    for ( int i = 1; i <= n; i ++ )
        scanf("%s", Map[i] + 1);
    
    memset(g, 0x3f, sizeof(g));
    f[startx][starty] = k, g[startx][starty] = 0;
    bin[0].push_back(Point(startx, starty));

    for ( int i = 0; i <= n * n + m; i ++ )
    {
        for ( auto now : bin[i] )
        {
            x = now.x, y = now.y;

            --x;
            if ( x >= 1 && Map[x][y] != '#' && g[x][y] == inf )
            {
                if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
                else
                    f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
            }
            ++x;

            ++x;
            if ( x <= n && Map[x][y] != '#' && g[x][y] == inf )
            {
                if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
                else
                    f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
            }
            --x;

            --y;
            if ( y >= 1 && Map[x][y] != '#' && g[x][y] == inf )
            {
                if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
                else
                    f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
            }
            ++y;

            ++y;
            if ( y <= m && Map[x][y] != '#' && g[x][y] == inf )
            {
                if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y], bin[g[x][y]].push_back(Point(x, y));
                else
                    f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
            }
            --y;
        }
    }

    unsigned long long ans = 0;
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= m; j ++ )
            if ( g[i][j] != inf )
                ans += 1uLL * g[i][j] * g[i][j];
    
    printf("%llu\n", ans);

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 27ms
memory: 258100kb

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: 23ms
memory: 256800kb

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: 36ms
memory: 258452kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 198ms
memory: 379948kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 281ms
memory: 355756kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 50ms
memory: 270408kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 71ms
memory: 269908kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 174ms
memory: 379760kb

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:

49803365625415

result:

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