QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#370526 | #8236. Snake Move | Arnold_6 | WA | 352ms | 58652kb | C++14 | 2.8kb | 2024-03-29 10:11:33 | 2024-03-29 10:11:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
int n,m,k;
char g[3001][3001];
bool vis[3001][3001];
int d[3001][3001];
int body[3001][3001];
int hx,hy;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dij()
{
d[hx][hy]=0;
// priority_queue<pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q;
queue<pair<int,pair<int,int> > >q1,q2;//body,notbody
q1.push({0,{hx,hy}});
while(q1.size() || q2.size())
{
int ans,x,y;
if(q1.size() && q2.size())
{
if(q1.front().first<q2.front().first)
{
ans=q1.front().first;
x=q1.front().second.first;
y=q1.front().second.second;
q1.pop();
}
else
{
ans=q2.front().first;
x=q2.front().second.first;
y=q2.front().second.second;
q2.pop();
}
}
else if(q1.size())
{
ans=q1.front().first;
x=q1.front().second.first;
y=q1.front().second.second;
q1.pop();
}
else
{
ans=q2.front().first;
x=q2.front().second.first;
y=q2.front().second.second;
q2.pop();
}
if(vis[x][y])continue;
vis[x][y]=1;
// cout<<endl<<x<<" "<<y<<" "<<ans<<endl;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1 || nx>n || ny<1 || ny>m || g[nx][ny]=='#')continue;
if(body[nx][ny]==0)
{
int tmp=d[x][y]+1;
if(tmp<d[nx][ny])
{
d[nx][ny]=tmp;
q2.push({tmp,{nx,ny}});
}
}
else
{
int tmp=max(d[x][y]+1,k-body[nx][ny]+1);
if(tmp<d[nx][ny])
{
d[nx][ny]=tmp;
q1.push({tmp,{nx,ny}});
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
body[x][y]=i;
if(i==1)hx=x,hy=y;
}
for(int i=1;i<=n;i++)cin>>g[i]+1;
memset(d,0x3f,sizeof(d));
dij();
ull sum=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(d[i][j]<0x3f3f3f3f && g[i][j]!='#')sum+=(ull)d[i][j]*d[i][j];
}
}
cout<<sum;
// system("pause");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38780kb
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: 3ms
memory: 38748kb
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: 38812kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 260ms
memory: 58652kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 352ms
memory: 58124kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 11ms
memory: 49780kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 8ms
memory: 49556kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 251ms
memory: 57504kb
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:
49803378854734
result:
wrong answer 1st lines differ - expected: '49803365625286', found: '49803378854734'