QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#324469#8236. Snake Moveucup-team484#WA 893ms74480kbC++171.5kb2024-02-10 19:49:032024-02-10 19:49:04

Judging History

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

  • [2024-02-10 19:49:04]
  • 评测
  • 测评结果:WA
  • 用时:893ms
  • 内存:74480kb
  • [2024-02-10 19:49:03]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef unsigned long long ll;
const int mod = 1e9 + 7;
const int N = 3e3 + 5;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, m, k; cin >> n >> m >> k;
	vector<pair<int, int>> a(k);
	vector<vector<int>> ans(n, vector<int>(m, mod)), vis(n, vector<int>(m, 0));
	for (int i = 0; i < k; i++) {
		cin >> a[i].first >> a[i].second;
		a[i].first--;
		a[i].second--;
		vis[a[i].first][a[i].second] = i;
	}
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		for (int j = 0; j < m; j++)
			if (s[j] == '#')
				vis[i][j] = -1;
	}
	ans[a[0].first][a[0].second] = 0;
	priority_queue<pair<int, pair<int, int>>> q;
	auto upd = [&](auto p, int d) {
		for (int i = 0; i < 4; i++) {
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];
			if (nx < 0 || ny < 0 || n <= nx || m <= ny || vis[nx][ny] == -1)
				continue;
			if ((vis[nx][ny] + d + 1 >= k || vis[nx][ny] == 0) && ans[nx][ny] > d + 1) {
				ans[nx][ny] = d + 1;
				q.push(make_pair(-d - 1, make_pair(nx, ny)));
			}
		}
	};
	q.push(make_pair(0, a[0]));
	int lo = 0;
	ll res = 0;
	while (!q.empty()) {
		auto [d, p] = q.top();
		q.pop();
		d = -d;
		if (p != a[0] && d != ans[p.first][p.second])
			continue;
		if (p != a[0])
			res += (ll)d * (ll)d;
		else if (d == lo && lo + 1 < k)
			q.push(make_pair(-(++lo), a[0]));
		upd(p, d);
	}

	cout << res << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 884ms
memory: 71848kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 833ms
memory: 71876kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 43ms
memory: 74180kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 40ms
memory: 71848kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 893ms
memory: 72096kb

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: 0
Accepted
time: 848ms
memory: 74480kb

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:

22509095749285

result:

ok single line: '22509095749285'

Test #10:

score: -100
Wrong Answer
time: 44ms
memory: 71804kb

input:

3000 2900 10
326 1781
325 1781
325 1782
325 1783
325 1784
324 1784
324 1783
323 1783
323 1782
324 1782
##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...

output:

41915

result:

wrong answer 1st lines differ - expected: '40571', found: '41915'