QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#328725#8236. Snake Moveyan_silva#WA 444ms154324kbC++201.8kb2024-02-16 03:09:532024-02-16 03:09:53

Judging History

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

  • [2024-02-16 03:09:53]
  • 评测
  • 测评结果:WA
  • 用时:444ms
  • 内存:154324kb
  • [2024-02-16 03:09:53]
  • 提交

answer

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

using ll = long long;

#define int ll
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

int imove[] = {-1, +1, 0, 0},
	jmove[] = {0, 0, -1, +1};

const int INF = 1e18;

signed main() {
	fastio;
	int n, m, k; cin>>n>>m>>k;
	
	pair<int,int> st;
	vector<vector<int>> val(n, vector<int>(m));
	for (int i = 1; i <= k; i++) {
		int x, y; cin>>x>>y; x--, y--;
		val[x][y] = k - i;
		if (i == 1) st = {x, y};
	}

	vector<string> grid(n);
	for (int i = 0; i < n; i++) {
		cin>>grid[i];
	}

	auto valid = [&](int i, int j) {
		return (0 <= i and i < n and 0 <= j and j < m and grid[i][j] == '.');
	};

	vector<vector<int>> dist(n, vector<int>(m, INF));
	
	priority_queue<array<int,3>> pq;
	queue<array<int,3>> q;
	q.push({0, st.first, st.second});
	dist[st.first][st.second] = 0;
	while (q.size()) {
		auto [d, i, j] = q.front();
		q.pop();

		while (pq.size() and pq.top()[0] == -d) {
			auto [cur_dist, ii, jj] = pq.top();
			if (-cur_dist == dist[ii][jj]) {
				q.push({-cur_dist, ii, jj});
			}
			pq.pop();
		}

		for (int k = 0; k < 4; k++) {
			int ii = i+imove[k],
				jj = j+jmove[k];

			if (valid(ii, jj)) {
				int t = max(0LL, val[ii][jj] - d) + d + 1;
				if (dist[ii][jj] > t) {
					dist[ii][jj] = t;
					if (t == d+1) {
						q.push({t, ii, jj});
					} else {
						pq.push({-t, ii, jj});
					}
				}
			}
		}
	}

	unsigned long long res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[i][j] != INF) {
				res += dist[i][j]*dist[i][j];
			}
		}
	}
	cout<<res<<'\n';

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 3632kb

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 363ms
memory: 149252kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 429ms
memory: 149292kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 28ms
memory: 154020kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 26ms
memory: 148812kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 347ms
memory: 149324kb

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: 444ms
memory: 154324kb

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: 0
Accepted
time: 16ms
memory: 148832kb

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:

40571

result:

ok single line: '40571'

Test #11:

score: -100
Wrong Answer
time: 19ms
memory: 149040kb

input:

2900 3000 10
2447 135
2447 136
2447 137
2447 138
2447 139
2447 140
2448 140
2448 139
2449 139
2449 138
.#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...

output:

251

result:

wrong answer 1st lines differ - expected: '2705', found: '251'