QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#638901 | #8236. Snake Move | HQLF | WA | 1393ms | 154504kb | C++20 | 4.2kb | 2024-10-13 17:15:57 | 2024-10-13 17:16:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ldb=long double;
using i128=__int128;
const ll maxn=4e5+50;
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll mod=998244353;
struct node
{
ll w;
ll x,y;
bool operator<(const node &t)const
{
return w>t.w;
}
};
ll vis[3010][3010];
char a[3010][3010];
ll f[3010][3010];
ll dx[10]={0,0,-1,1};
ll dy[10]={-1,1,0,0,};
void solve()
{
ll n,m,k;
cin>>n>>m>>k;
pair<ll,ll> snk[k+10];
for(ll i=1;i<=k;i++)
{
cin>>snk[i].first>>snk[i].second;
}
for(ll i=0;i<=3005;i++)
{
for(ll j=0;j<=3005;j++)
{
vis[i][j]=0;
f[i][j]=inf;
a[i][j]=0;
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
ll ci=max(0ll,k-2);
priority_queue<node>q;
node t;
t.w=ci;
t.x=snk[1].first;
t.y=snk[1].second;
q.push(t);
f[t.x][t.y]=ci;
while(!q.empty())
{
node tp=q.top();
q.pop();
ll w=tp.w;
ll x=tp.x;
ll y=tp.y;
if(vis[x][y]==1)continue;
vis[x][y]=1;
for(ll i=0;i<=3;i++)
{
ll tx=x+dx[i];
ll ty=y+dy[i];
if(f[tx][ty]>f[x][y]+1&&a[tx][ty]=='.')
{
f[tx][ty]=f[x][y]+1;
if(vis[tx][ty]==0)
{
t.w=f[tx][ty];
t.x=tx;
t.y=ty;
q.push(t);
}
}
}
}
f[snk[1].first][snk[1].second]=0;
for(ll i=1;i<=k-1;i++)
{
ll x=snk[i].first;
ll y=snk[i].second;
a[x][y]='#';
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
vis[i][j]=0;
}
}
t.w=0;
t.x=snk[1].first;
t.y=snk[1].second;
q.push(t);
while(!q.empty())
{
node tp=q.top();
q.pop();
ll w=tp.w;
ll x=tp.x;
ll y=tp.y;
if(vis[x][y]==1)continue;
vis[x][y]=1;
for(ll i=0;i<=3;i++)
{
ll tx=x+dx[i];
ll ty=y+dy[i];
if(f[tx][ty]>f[x][y]+1&&a[tx][ty]=='.')
{
f[tx][ty]=f[x][y]+1;
if(vis[tx][ty]==0)
{
t.w=f[tx][ty];
t.x=tx;
t.y=ty;
q.push(t);
}
}
}
}
for(ll i=k-1;i>=2;i--)
{
ll x=snk[i].first;
ll y=snk[i].second;
ll w=ci+(i-1);
for(ll j=0;j<=3;j++)
{
ll tx=x+dx[j];
ll ty=y+dy[j];
ll tw=k-i;
if(a[tx][ty]=='.'&&f[tx][ty]!=inf)
{
ll cha=tw-f[tx][ty];
cha=max(0ll,cha);
ll ttw=f[tx][ty]+cha+1;
w=min(w,ttw);
}
}
f[x][y]=w;
a[x][y]='.';
}
for(ll i=1;i<=k;i++)
{
ll x=snk[i].first;
ll y=snk[i].second;
a[x][y]='*';
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
if(f[i][j]!=inf&&a[i][j]=='.')
{
f[i][j]=min({f[i][j],f[i][j-1]+1,f[i][j+1]+1,f[i-1][j]+1,f[i+1][j]+1});
}
}
}
// for(ll i=1;i<=n;i++)
// {
// for(ll j=1;j<=m;j++)
// {
// if(f[i][j]==inf)
// {
// printf(" inf");
// }
// else printf("%4lld",f[i][j]);
// }
// printf("\n");
// }
// printf("\n");
ull ans=0;
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
if(f[i][j]==inf)ans+=0;
else ans+=(f[i][j]*f[i][j]);
}
}
printf("%llu\n",ans);
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ll _=1;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 154140kb
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: 12ms
memory: 154076kb
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: 4ms
memory: 154092kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 755ms
memory: 154504kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 733ms
memory: 154252kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 84ms
memory: 154116kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 76ms
memory: 154148kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 1393ms
memory: 154288kb
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:
49803413395762
result:
wrong answer 1st lines differ - expected: '49803365625286', found: '49803413395762'