QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594839#8236. Snake MoveabsabsWA 576ms225392kbC++234.2kb2024-09-28 10:36:492024-09-28 10:37:02

Judging History

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

  • [2024-09-28 10:37:02]
  • 评测
  • 测评结果:WA
  • 用时:576ms
  • 内存:225392kb
  • [2024-09-28 10:36:49]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cout << #x << "=" << x << endl
// using i128 = __int128_t;
#define int unsigned long long
typedef pair<int, int> PII;
typedef long long ll;
inline void read(int &x)
{
    char ch = getchar();
    int f = 1;
    x = 0;
    while (!isdigit(ch) && ch ^ '-')
        ch = getchar();
    if (ch == '-')
        f = -1, ch = getchar();
    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
// int a[N];
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
#define pre(i, a, b) for (int i = a; i <= b; i++)
int qmi(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll ans[N];
ll n, m, k;
ll tim[3010][3010];
char v[3010][3010];
ll dist[3010][3010];
ll dx[] = {1, -1, 0, 0};
ll dy[] = {0, 0, 1, -1};
ll vis[3010][3010];
ll st[3010][3010];
queue<PII> q;
void rCL()
{
    cin >> n >> m >> k;
    // cout<<n<<endl;
    // return;
    vector<PII> poi;
    int aa, bb;
    for (int i = 1; i <= k; i++)
    {
        int a, b;
        cin >> a >> b;
        poi.push_back({a, b});
        if (i == 1)
        {
            aa = a;
            bb = b;
            continue;
        }
        // if (i == 1)
        //     continue;
        // if (i != k)
            tim[a][b] = k - i + 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> v[i][j];
        }
    }

    vis[aa][bb] = 1;
    q.push({aa, bb});
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 1 || xx > n || yy<1 | yy> m || v[xx][yy] == '#' || vis[xx][yy])
                continue;
            if (dist[x][y] + 1 < tim[xx][yy])
                continue;
            q.push({xx, yy});
            vis[xx][yy] = 1;
            dist[xx][yy] = dist[x][y] + 1;
        }
    }
    if (poi.size() > 2)
        poi.pop_back();
    for (int i = 0; i < poi.size(); i++)
    {
        if (i == 0)
            continue;
        int a = poi[i].first;
        int b = poi[i].second;
        st[a][b] = 1;
        dist[a][b] = k + i - 2;
        q.push({a, b});
    }

    /////
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        // cout<<xx<<" "<<yy<<endl;
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 1 || xx > n || yy<1 | yy> m || v[xx][yy] == '#' || st[xx][yy])
                continue;
            if (dist[x][y] + 1 < tim[xx][yy])
                continue;
            q.push({xx, yy});
            st[xx][yy] = 1;
            dist[xx][yy] = min(dist[xx][yy], dist[x][y] + 1);
        }
    }

    ///
    reverse(poi.begin(), poi.end());
    if (poi.size() > 2)
        poi.pop_back();
    for (auto [a, b] : poi)
    {
        for (int i = 0; i < 4; i++)
        {
            int xx = a + dx[i];
            int yy = b + dy[i];
            if (xx < 1 || xx > n || yy<1 | yy> m || v[xx][yy] == '#')
                continue;
            if (dist[xx][yy] + 1 < tim[a][b])
                continue;
            dist[a][b] = min(dist[xx][yy] + 1, dist[a][b]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i == aa && j == bb)
            {
                continue;
            }
            int qwq = max(dist[i][j], (tim[i][j]));
            qwq = dist[i][j];
            ans += qwq * qwq;
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int O_o = 1;
    // cin >> O_o;
    while (O_o--)
    {
        rCL();
    }
}

詳細信息

Test #1:

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

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: 1ms
memory: 12060kb

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: 1ms
memory: 11800kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 291ms
memory: 156168kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 364ms
memory: 153844kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 55ms
memory: 18320kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 61ms
memory: 17972kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 576ms
memory: 225392kb

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:

49803365625314

result:

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