QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#593984 | #8236. Snake Move | absabs | WA | 585ms | 223980kb | C++23 | 5.6kb | 2024-09-27 17:46:44 | 2024-09-27 17:46:44 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cout << #x << "=" << x << endl
// using i128 = __int128_t;
#define int unsigned long long
typedef pair<int, int> PII;
typedef long long ll;
inline void read(int &x)
{
char ch = getchar();
int f = 1;
x = 0;
while (!isdigit(ch) && ch ^ '-')
ch = getchar();
if (ch == '-')
f = -1, ch = getchar();
while (isdigit(ch))
x = x * 10 + ch - '0', ch = getchar();
x *= f;
}
void write(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
// int a[N];
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
#define pre(i,a,b) for(int i=a;i<=b;i++)
int qmi(int a,int b)
{
int res = 1;
while(b)
{
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
// struct node
// {
// int a,b,c;
// }a[N];
ll ans[N];
ll n,m,k;
ll tim[3010][3010];
char v[3010][3010];
ll dist[3010][3010];
ll dx[]={1,-1,0,0};
ll dy[]={0,0,1,-1};
ll vis[3010][3010];
ll st[3010][3010];
queue<PII>q;
void rCL()
{
cin>>n>>m>>k;
// cout<<n<<endl;
// return;
vector<PII>poi;
int aa,bb;
for(int i=1;i<=k;i++){
int a,b;
cin>>a>>b;
poi.push_back({a,b});
if(i==1){
aa=a;
bb=b;
}
if(i==1)continue;
if(i!=k)tim[a][b]=k-i+1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>v[i][j];
}
}
vis[aa][bb]=1;
q.push({aa,bb});
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
// cout<<xx<<" "<<yy<<endl;
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||vis[xx][yy])continue;
if(dist[xx][yy]+1<tim[xx][yy])continue;
q.push({xx,yy});
vis[xx][yy]=1;
dist[xx][yy]=dist[x][y]+1;
}
}
//////////////////
// q.push({aa,bb});
// for(int i=1;i<4;i++)
// {
// int xx=aa+dx[i];
// int yy=bb+dy[i];
// if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||dist[xx][yy] != 0)continue;
// q.push({xx,yy});
// }
// for(auto [a,b]:poi){
// q.push({a,b});
// }
// while(!q.empty())
// {
// int x=q.front().first;
// int y=q.front().second;
// q.pop();
// // cout << x << " tttt " << y << endl;
// // cout<<xx<<" "<<yy<<endl;
// for(int i=0;i<4;i++){
// int xx=x+dx[i];
// int yy=y+dy[i];
// if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||dist[xx][yy]==0)continue;
// if(dist[xx][yy]+1<tim[x][y])continue;
// // q.push({xx,yy});
// // st[xx][yy]=1;
// // dist[xx][yy]=min(dist[xx][yy],dist[x][y]+1);
// if(dist[x][y])dist[x][y]=min(dist[xx][yy]+1,dist[x][y]);
// else dist[x][y]=dist[xx][yy]+1;
// }
// }
////////////////
// for(int i=0;i<poi.size();i++)
// {
// int a=poi[i].first;
// int b=poi[i].second;
// st[a][b] = 1;
// }
if(poi.size() > 1) poi.pop_back();
for(int i=0;i<poi.size();i++){
if(i==0)continue;
int a=poi[i].first;
int b=poi[i].second;
st[a][b]=1;
dist[a][b]=k+i-2;
q.push({a,b});
}
/////
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
// cout<<xx<<" "<<yy<<endl;
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||st[xx][yy])continue;
// if(dist[xx][yy]+1<tim[xx][yy])continue;
q.push({xx,yy});
st[xx][yy]=1;
dist[xx][yy]=min(dist[xx][yy],dist[x][y]+1);
}
}
///
reverse(poi.begin(),poi.end());
if(poi.size() > 2)poi.pop_back();
for(auto [a,b]:poi){
// cout<<endl;
// cout<<a<<" "<<b<<endl;
for(int i=0;i<4;i++){
int xx=a+dx[i];
int yy=b+dy[i];
if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#')continue;
// cout<<xx<<" "<<yy<<endl;
// cout<<dist[xx][yy]+1<<" "<<tim[a][b]<<endl<<endl;;
if(dist[xx][yy]+1<tim[a][b])continue;
dist[a][b]=min(dist[xx][yy]+1,dist[a][b]);
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
// cout<<dist[i][j]<<" ";
if(i==aa&&j==bb){
continue;
}
int qwq=max(dist[i][j],(tim[i][j]));
qwq=dist[i][j];
ans+=qwq*qwq;
// cout<<qwq*qwq<<endl;
}
// cout<<endl;
}
// cout<<endl;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<tim[i][j]<<" ";
// if(i==aa&&j==bb){
// continue;
// }
// int qwq=max(dist[i][j],(tim[i][j]+1));
// ans+=qwq*qwq;
// // cout<<qwq*qwq<<endl;
// }
// cout<<endl;
// }
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int O_o = 1;
// cin >> O_o;
while (O_o--)
{
rCL();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 12068kb
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: 14080kb
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: 11756kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 314ms
memory: 156804kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 404ms
memory: 152224kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 60ms
memory: 18048kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 63ms
memory: 17864kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 585ms
memory: 223980kb
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:
49803413398430
result:
wrong answer 1st lines differ - expected: '49803365625286', found: '49803413398430'