QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#324476#8236. Snake Moveucup-team484#TL 1938ms74372kbC++171.4kb2024-02-10 19:52:332024-02-10 19:52:33

Judging History

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

  • [2024-02-10 19:52:33]
  • 评测
  • 测评结果:TL
  • 用时:1938ms
  • 内存:74372kb
  • [2024-02-10 19:52:33]
  • 提交

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]));
	ll res = 0;
	while (!q.empty()) {
		auto [d, p] = q.top();
		q.pop();
		d = -d;
		if (d < ans[p.first][p.second] + k)
			q.push(make_pair(-(d + 1), p));
		if (d == ans[p.first][p.second])
			res += (ll)d * (ll)d;
		upd(p, d);
	}
	cout << res << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 1938ms
memory: 72164kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 1663ms
memory: 71856kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 45ms
memory: 74372kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 39ms
memory: 72012kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Time Limit Exceeded

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:


result: