QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345149#8236. Snake Moveoscaryang#TL 2ms9888kbC++201.7kb2024-03-06 11:11:092024-03-06 11:11:09

Judging History

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

  • [2024-03-06 11:11:09]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:9888kb
  • [2024-03-06 11:11:09]
  • 提交

answer

#include<bits/stdc++.h>

#define ull unsigned long long
#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 3005, inf = 1e9;
const int dx[5] = {1, -1, 0, 0}, dy[5] = {0, 0, 1, -1};

int n, m, k, sx, sy, a[N][N], f[N][N], vis[N][N];
ull ans;
char Map[N][N];

inline void bfs(int len) {
	queue<tuple<int, int, int> > Q; 
	f[sx][sy] = k - len;
	Q.push(make_tuple(sx, sy, 0));
	
	auto ok = [&](int x, int y, int d) -> int {
		if(x <= 0 || x > n || y <= 0 || y > m) return 0;
		if(Map[x][y] == '#' || d + k - len >= f[x][y]) return 0;
		if(a[x][y] && a[x][y] <= len && len - a[x][y] >= d) return 0;
		return 1;
	};
	
	while(!Q.empty()) {
		auto [x, y, d] = Q.front(); Q.pop();
		for(int i = 0, nx = x + dx[i], ny = y + dy[i]; i < 4; i++, nx = x + dx[i], ny = y + dy[i])
			if(ok(nx, ny, d + 1)) 
				vis[nx][ny] = len, f[nx][ny] = d + k - len + 1, Q.push(make_tuple(nx, ny, d + 1));
	}
}

signed main() {
	n = read(); m = read(); k = read();
	for(int i = 1, u, v; i <= k; i++) {
		u = read(), v = read(), a[u][v] = i;
		if(i == 1) sx = u, sy = v;
	}
	rep(i, 1, n) scanf("%s", Map[i] + 1);
	
	rep(i, 1, n) rep(j, 1, m) f[i][j] = inf;
	
	rep(i, 1, k) bfs(i);
	
	rep(i, 1, n) rep(j, 1, m) if(f[i][j] != inf) 
		ans += 1ull * f[i][j] * f[i][j], cerr << i << " " << j << " " << f[i][j] << endl;
	cout << ans << endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Time Limit Exceeded

input:

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

output:


result: