QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#638413#8236. Snake MoveyangrunWA 610ms86648kbC++171.6kb2024-10-13 15:52:142024-10-13 15:52:19

Judging History

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

  • [2024-10-13 15:52:19]
  • 评测
  • 测评结果:WA
  • 用时:610ms
  • 内存:86648kb
  • [2024-10-13 15:52:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define uint unsigned long long
int read() {
  int res = 0, flg = 1;
  char c = getchar();
  while(!isdigit(c)) {
    if(c == '-') flg = 0;
    c = getchar();
  }
  while(isdigit(c)) {
    res = (res << 3) + (res << 1) + (c ^ 48);
    c = getchar();
  }
  return flg ? res : -res;
}
const int N = 3e3 + 10;
struct Node{
  int x, y, d;
  bool operator < (const Node& other) const{
    return d > other.d;
  }
};
priority_queue<Node> q;
int n, m, k; 
int f[N][N], vis[N][N];
char ma[N][N];
int nxt[5] = {0, 1, 0, -1, 0};
signed main() {
  memset(f, 0x3f, sizeof f);
  memset(ma, '#', sizeof ma);
  n = read(), m = read(), k = read();
  
  
  int x, y, d;
  x = read(), y = read();
  f[x][y] = 0;
  q.push({x, y, 0});
  for(int i = k - 1; i; --i) {
    x = read(), y = read();
    vis[x][y] = i;
  }
  
  for(int i = 1; i <= n; ++i) {
    scanf("%s", ma[i] + 1);
  }
  
  while(q.size()) {
    Node cur = q.top();
    q.pop();
    x = cur.x, y = cur.y;
    d = cur.d;
    
    for(int i = 0; i < 4; ++i) {
      int xx = x + nxt[i], yy = y + nxt[i + 1];
      if(ma[xx][yy] == '#') continue;
      int dd = max(d + 1, vis[xx][yy]);
      if(dd < f[xx][yy]) {
        f[xx][yy] = dd;
        q.push({xx, yy, dd});
      }
    }
  }
  
  uint res = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      if(vis[i][j] == -1 || f[i][j] > k * n * n) continue;
      res += f[i][j] * f[i][j];
    }
  }
  cout << res << '\n'; 
  return 0;
}

詳細信息

Test #1:

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

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: 3ms
memory: 84596kb

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: 3ms
memory: 84412kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 610ms
memory: 84544kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: -100
Wrong Answer
time: 558ms
memory: 84680kb

input:

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

output:

17465455560435

result:

wrong answer 1st lines differ - expected: '17464052497724', found: '17465455560435'