QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590065#8236. Snake MoveSLF666WA 860ms82024kbC++171.7kb2024-09-25 21:22:412024-09-25 21:22:41

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 21:22:41]
  • 评测
  • 测评结果:WA
  • 用时:860ms
  • 内存:82024kb
  • [2024-09-25 21:22:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define endl "\n"

const int N = 5e5 + 5, inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

struct node{
	int x,y,dis;
	bool operator < (const node &slf)const{
		return dis > slf.dis;
	}
}; 

int nx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void solve(){
	int n,m,k;
	cin>>n>>m>>k;
	vector<vector<int>>vis(n+1, vector<int>(m+1));
	vector<vector<char>>g(n+1, vector<char>(m+1));
	vector<vector<int>>dis(n+1, vector<int>(m+1, inf));
	vector<vector<bool>>book(n+1, vector<bool>(m+1));
	priority_queue<node>q;
	for(int i=1,x,y;i<=k;i++){
		cin>>x>>y;
		vis[x][y] = i;
		if(i == 1){
			q.push({x, y, 0});
			dis[x][y] = 0;
		}
	}
	
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		cin>>g[i][j];
	}
	
	while(!q.empty()){
		auto [x, y, d] = q.top();
		q.pop();
		
		if(book[x][y])continue;
		book[x][y] = 1;
		
		for(int i=0;i<4;i++){
			int dx = x + nx[i][0];
			int dy = y + nx[i][1];
			if(dx < 0 || dx > n || dy < 0 || dy > m)continue;
			if(g[dx][dy] == '#' || book[dx][dy])continue;
			if(vis[dx][dy] > 1){
				int t = max(k - vis[dx][dy], d) + 1;
				if(dis[dx][dy] > t){
					q.push({dx, dy, t});
					dis[dx][dy] = t;
				}
			}
			else if(dis[dx][dy] > d + 1){
				q.push({dx, dy, d + 1});
				dis[dx][dy] = d + 1;
			}
		}
	}
	
	ull ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
//			cout<<dis[i][j]<<" ";
			if(dis[i][j] == inf)continue;
			ans += (ull)dis[i][j] * (ull)dis[i][j];
		}//cout<<endl;
	}
	cout<<ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
//	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

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: 3780kb

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: 3628kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 860ms
memory: 82024kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: -100
Wrong Answer
time: 727ms
memory: 81680kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17470812522819

result:

wrong answer 1st lines differ - expected: '17464052497724', found: '17470812522819'