QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323859 | #8236. Snake Move | ucup-team987# | TL | 225ms | 49532kb | C++20 | 1.3kb | 2024-02-10 13:50:22 | 2024-02-10 13:50:23 |
Judging History
answer
#include<iostream>
#include<queue>
#include<cassert>
using namespace std;
const int d[5]={0,1,0,-1};
int H,W,N;
int dist[3000][3000];
int need[3000][3000];
string S[3000];
int sx,sy;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>H>>W>>N;
for(int i=0;i<H;i++)for(int j=0;j<W;j++)dist[i][j]=1e9;
cin>>sx>>sy;sx--,sy--;
for(int i=1;i<N;i++)
{
int x,y;cin>>x>>y;
x--,y--;
need[x][y]=N-i;
}
for(int i=0;i<H;i++)cin>>S[i];
dist[sx][sy]=0;
priority_queue<pair<int,int> >BODY;
vector<int>A,B;
A.push_back(sx*W+sy);
for(int nd=0;;nd++)
{
if(A.empty()&&BODY.empty())break;
while(!BODY.empty()&&BODY.top().first==nd)
{
A.push_back(BODY.top().second);
BODY.pop();
}
assert(B.empty());
for(int u:A)
{
int x=u/W,y=u%W;
for(int r=0;r<4;r++)
{
int tx=x+d[r],ty=y+d[r+1];
if(tx<0||ty<0||tx>=H||ty>=W||S[tx][ty]=='#'||dist[tx][ty]<=nd+1)continue;
dist[tx][ty]=nd+1;
if(nd+1<need[tx][ty])BODY.push(make_pair(need[tx][ty],tx*W+ty));
else B.push_back(tx*W+ty);
}
}
A.clear();
swap(A,B);
}
unsigned long long ans=0;
for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(dist[i][j]<(int)1e9)
{
unsigned long long t=max(dist[i][j],need[i][j]);
ans+=t*t;
}
cout<<ans<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
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: 5732kb
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: 5716kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 127ms
memory: 48860kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 225ms
memory: 47788kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 84ms
memory: 49532kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 89ms
memory: 48220kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Time Limit Exceeded
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................