QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661569 | #8236. Snake Move | Lemon | WA | 1020ms | 952640kb | C++14 | 2.1kb | 2024-10-20 16:53:37 | 2024-10-20 16:53:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=8e7;
const int N=9e6+5;
const ull inf=1e18;
int hd[N],cnt,n,m,k,stx,sty,vis[N];
char s[3005][3005];
ull dis[N],len[N];
ull ans;
struct edge{
int u,to,nxt;
}e[maxn];
void add(int u,int v){
e[++cnt].nxt=hd[u];
e[cnt].to=v;
e[cnt].u=u;
hd[u]=cnt;
}
int pos(int x,int y){
return (x-1)*m+y;
}
queue<int>q;
void bfs(int x,int y){
q.push(pos(x,y));
vis[pos(stx,sty)]=1;
dis[pos(stx,sty)]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>=max(dis[u]+1,len[v]+1)){
dis[v]=max(dis[u]+1,len[v]+1);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dis[pos(i,j)]=inf;
}
}
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
if(i==1) stx=x,sty=y;
len[pos(x,y)]=k-i;
}
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='#') continue;
if(s[i-1][j]=='.'){
add(pos(i,j),pos(i-1,j));
add(pos(i-1,j),pos(i,j));
}
if(s[i][j-1]=='.'){
add(pos(i,j),pos(i,j-1));
add(pos(i,j-1),pos(i,j));
}
if(s[i+1][j]=='.'){
add(pos(i,j),pos(i+1,j));
add(pos(i+1,j),pos(i,j));
}
if(s[i][j+1]=='.'){
add(pos(i,j),pos(i,j+1));
add(pos(i,j+1),pos(i,j));
}
}
}
bfs(stx,sty);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dis[pos(i,j)]==inf) continue;
ans+=(dis[pos(i,j)]*dis[pos(i,j)]);
}
}
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 13952kb
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: 14232kb
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: 2ms
memory: 13868kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 1020ms
memory: 950932kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 817ms
memory: 546152kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 130ms
memory: 330784kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 63ms
memory: 195256kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 946ms
memory: 952640kb
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:
49803365625286
result:
ok single line: '49803365625286'
Test #9:
score: -100
Wrong Answer
time: 766ms
memory: 560712kb
input:
3000 3000 10 2015 1932 2015 1931 2015 1930 2015 1929 2016 1929 2017 1929 2018 1929 2018 1928 2018 1927 2017 1927 #...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......
output:
22509095749317
result:
wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749317'