QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618413 | #8236. Snake Move | E7k | WA | 1ms | 3828kb | C++20 | 2.3kb | 2024-10-06 21:54:02 | 2024-10-06 21:54:05 |
Judging History
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'