QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#587135#8236. Snake MoveSLF666#WA 663ms154680kbC++171.9kb2024-09-24 17:44:342024-09-24 17:44:34

Judging History

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

  • [2024-09-24 17:44:34]
  • 评测
  • 测评结果:WA
  • 用时:663ms
  • 内存:154680kb
  • [2024-09-24 17:44:34]
  • 提交

answer

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

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

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

void solve(){
	ull n, m, k;
	cin >> n >> m >> k;
	map<pair<int, int>, ull> mp;
	int i;
	int nowx1 = -1, nowy1 = -1;
	int nowx2 = -1, nowy2 = -1;
	for(i = 0 ; i < k ; i ++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		if(i == 0) {
			nowx1 = x;
			nowy1 = y;
		}
		if(i == 1) {
			nowx2 = x;
			nowy2 = y;
		}
		if(i != 0) mp[{x, y}] = k - i;
	}
	vector<vector<ull>> f1(n + 3, vector<ull>(m + 3, 1e18));
	vector<vector<ull>> book(n + 3, vector<ull>(m + 3, 0));
	vector<string> a(n + 3);
	int j;
	for(i = 0 ; i < n ; i ++) {
		cin >> a[i];
	}
	
	queue<pair<ull, pair<int, int>>> q;
//	priority_queue<pair<ull, pair<int, int>>, vector<pair<ull, pair<int, int>>>, greater<pair<ull, pair<int, int>>> > q;
	q.push({0, {nowx1, nowy1}});
	while(!q.empty()) {
		auto it = q.front();
		q.pop();
		int x = it.second.first;
		int y = it.second.second;
		ull step = it.first;
		if(x < 0 || y < 0 || x >= n || y >= m) continue;
		if(a[x][y] == '#') continue;
		f1[x][y] = min(f1[x][y], step);
		if(mp.count({x, y})) {
			f1[x][y] = max(mp[{x, y}], f1[x][y]);
		}
		if(book[x][y]) continue;
		book[x][y] = 1;
		for(i = 0 ; i < 4 ; i ++) {
			int nx = x + nt[i][0], ny = y + nt[i][1];
			int ss = f1[x][y] + 1;
			q.push({ss, {nx, ny}});
		}
	}
	
	for(i = 0 ; i <= n ; i ++) {
		for(j = 0 ; j <= m ; j ++) book[i][j] = 0;
	}
	
	ull ans = 0;
	
	for(i = 0 ; i < n ; i ++) {
		for(j = 0 ; j < m ; j ++) {
			if(f1[i][j] == 1e18) continue;
			ans += f1[i][j] * f1[i][j];
//			cout << f1[i][j] << ' ';
		}
//		cout << endl;
	}
	
	cout << ans << endl;
	
}

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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 587ms
memory: 149920kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 609ms
memory: 149556kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 35ms
memory: 154048kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 35ms
memory: 149092kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 636ms
memory: 149876kb

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: 663ms
memory: 154680kb

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'