QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#680910#8236. Snake Move1ockhartWA 418ms159672kbC++202.0kb2024-10-26 23:29:192024-10-26 23:29:20

Judging History

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

  • [2024-10-26 23:29:20]
  • 评测
  • 测评结果:WA
  • 用时:418ms
  • 内存:159672kb
  • [2024-10-26 23:29:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")

using ll = long long;
//using i128 = __int128_t;
#define endl "\n"
#define int long long
#define db cout << "db" << endl;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 3010;
ll inf = 2e18;
int n, m, k;
int a[N], b[N], dis[M][M], ma[M][M], vis[M][M];
string s[M];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int x, int y) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dis[i][j] = inf;
		}
	}
	dis[x][y] = 0;
	queue<PII> q;
	q.push({x, y});
	while (q.size()) {
		int x1 = q.front().x, y1 = q.front().y;
		q.pop();

		if (vis[x1][y1]) {
			continue;
		}
		vis[x1][y1] = 1;
		for (int i = 0; i < 4; i++) {
			int x2 = x1 + dx[i], y2 = y1 + dy[i];
			if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || s[x2][y2] == '#') {
				continue;
			} else if (ma[x2][y2] && dis[x1][y1] < k - ma[x2][y2]) {
				dis[x2][y2] = min(dis[x2][y2], k - ma[x2][y2] + 1);
				q.push({x2, y2});
			} else if (dis[x2][y2] > dis[x1][y1] + 1){
				dis[x2][y2] = dis[x1][y1] + 1;
				q.push({x2, y2});
			}
		}

	}
}
void solve() {
    
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
    	cin >> a[i] >> b[i];
    	a[i]--; b[i]--;
    	ma[a[i]][b[i]] = i;
    }
    for (int i = 0; i < n; i++) {
    	cin >> s[i];
    }
    bfs(a[1], b[1]);
    for (int i = 2; i <= k; i++) {
    	dis[a[i]][b[i]] = max(dis[a[i]][b[i]], k - i);
    }

    int ans = 0;

    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < m; j++) {
    		int x = dis[i][j];
    		if (x != inf) {
    			ans += x * x;
    			//cout << i + 1 << " " << j + 1 << " " << x * x << endl;
    		}

    	}
    }

    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int q = 1;
    //cin >> q;
    while (q --) {
        solve();
    }
    return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9868kb

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 341ms
memory: 159372kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 399ms
memory: 157132kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 17ms
memory: 87120kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 24ms
memory: 86472kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 350ms
memory: 155012kb

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: 418ms
memory: 159672kb

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'