QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#664560 | #8236. Snake Move | chenkaiwen | WA | 493ms | 178108kb | C++14 | 2.4kb | 2024-10-21 21:11:50 | 2024-10-21 21:11:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
__int128 Read() {
__int128 w=0,f=1;
char c=getchar();
while(c>'9'||c<'0') {
if(c=='-')f*=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
w=w*10+c-'0';
c=getchar();
}
return w*f;
}
string Write(__int128 x) {
string s="";
bool f=0;
if(x<0)f=1,x=x*-1;
while(x) {
s=(char)(x%10+'0')+s;
x=x/10;
}
if(!s.size())s="0";
return (f?"-":"")+s;
}
#define int long long
int n,m,k;
string s[3030];
__int128 dis[3030][3030];
int sk[3030][3030];
struct as {
int x,y,d;
};
const int FX[4]= {0,0,1,-1},FY[4]= {1,-1,0,0};
#define D(X) dis[X.x][X.y]
#define T(X,i,ds) ((as){X.x+FX[i],X.y+FY[i],ds})
#define S(X) ((bool)(s[X.x][X.y]=='.'))
queue<as>q1,q2;
bool vis[3030][3030];
void DIJ(as rt) {
for(int i=0; i<=n+1; i++)for(int j=0; j<=m+2; j++)dis[i][j]=1e9+7;
// cout<<"QAQ\n";
D(rt)=0;
q1.push(rt);
while(q1.size()||q2.size()) {
// cout<<"QAQ1\n";
as u,v;
if(q1.size()&&q2.size()) {
if(D(q1.front())<D(q2.front())) {
u=q1.front();
q1.pop();
} else {
u=q2.front();
q2.pop();
}
} else {
if(q1.size()) {
u=q1.front();
q1.pop();
} else {
u=q2.front();
q2.pop();
}
}
// if(u.d!=D(u))continue;
if(vis[u.x][u.y])continue;
vis[u.x][u.y]=1;
// cout<<u.x<<" "<<u.y<<endl;
for(int i=0; i<4; i++) {
v=T(u,i,0);
if(!S(v))continue;
if(sk[v.x][v.y]) {
if(D(v)>max(D(u)+1ll,(__int128)(k-sk[v.x][v.y]+1))) {
D(v)=max(D(u)+1ll,(__int128)(k-sk[v.x][v.y]+1));
v.d=D(v);
if(!vis[v.x][v.y])q2.push(v);
}
} else {
if(D(v)>D(u)) {
D(v)=D(u)+1;
v.d=D(v);
// if(!vis[v.x][v.y])
if(!vis[v.x][v.y])q1.push(v);
}
}
}
}
}
int stx,sty;
void Work() {
cin>>n>>m>>k;
for(int i=1; i<=k; i++) {
int t1,t2;
cin>>t1>>t2;
sk[t1][t2]=i;
if(i==1)stx=t1,sty=t2;
}
for(int i=1; i<=n; i++) {
cin>>s[i];
s[i]="#"+s[i]+"#";
}
for(int i=0; i<=m+1; i++)s[0]=s[0]+"#",s[n+1]=s[n+1]+"#";
// for(int i=0; i<=n+1; i++)cout<<s[i]<<endl;
DIJ((as) {
stx,sty,0
});
__int128 ans=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++){
if(dis[i][j]>1e9)dis[i][j]=0;
// cout<<dis[i][j]<<" ";
ans+=dis[i][j]*dis[i][j];
}
// cout<<"\n";
}
cout<<Write(ans)<<endl;
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
Work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7964kb
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: 7824kb
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: 8040kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 397ms
memory: 176304kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 493ms
memory: 173424kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 44ms
memory: 169216kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 35ms
memory: 168568kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 431ms
memory: 172372kb
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: 474ms
memory: 178108kb
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'