QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618413#8236. Snake MoveE7kWA 1ms3828kbC++202.3kb2024-10-06 21:54:022024-10-06 21:54:05

Judging History

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

  • [2024-10-06 21:54:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3828kb
  • [2024-10-06 21:54:02]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define gcd __gcd
using namespace std;
typedef pair<int,int> pii;
const int INF = 9e18;
const int inf = 2e9;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int qmi(int a,int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
int inv(int x)
{
    return qmi(x,mod-2);
}
int MOD(int x)
{
    return (x % mod + mod) % mod;
}
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n ,m,k;
    cin >> n>> m >> k;
    vector<array<int,2>> e(k + 1);
    for(int i = 1;i <= k;i ++) cin >> e[i][0] >> e[i][1];
    vector<vector<int>> dist(n + 1,vector<int> (m + 1,INF)),vis(n + 1,vector<int> (m + 1));
    vector<vector<int>> f(n + 1,vector<int> (m + 1));
    for(int i = 1;i <= k;i ++) f[e[i][0]][e[i][1]] = i;

    vector<string> g(n + 1);
    for(int i = 1;i <= n;i ++) cin >> g[i];
    for(int i = 1;i <= n;i ++) g[i] = " " + g[i];
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> heap;
    heap.push({dist[e[1][0]][e[1][1]],e[1][0],e[1][1]});
    dist[e[1][0]][e[1][1]] = 0;

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int x = t[1],y = t[2];
        if(vis[x][y]) continue;
        vis[x][y] = 1;

        for(int i = 0;i < 4;i ++)
        {
            int xx = x + dx[i],yy = y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
            if(g[xx][yy] == '#' || vis[xx][yy]) continue;
            if(dist[xx][yy] > dist[x][y] + 1)
            {
                dist[xx][yy] = dist[x][y] + 1;
                if(f[xx][yy]> 0) dist[xx][yy] = max(dist[xx][yy],k - f[xx][yy] + 1);
                heap.push({dist[xx][yy],xx,yy});
            }
        }
    }

    // for(int i = 1;i <= n;i ++)
    // {
    //     for(int j = 1;j <= m;j ++)
    //     {
    //         cout << dist[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    unsigned long long ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            ans += dist[i][j] * dist[i][j];
        }
    }
    cout << ans << endl;
 }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

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

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3828kb

input:

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

output:

10545165951823774103

result:

wrong answer 1st lines differ - expected: '407', found: '10545165951823774103'