QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#775903#8236. Snake MovedodolaWA 1054ms96804kbC++172.8kb2024-11-23 17:01:102024-11-23 17:01:10

Judging History

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

  • [2024-11-23 17:01:10]
  • 评测
  • 测评结果:WA
  • 用时:1054ms
  • 内存:96804kb
  • [2024-11-23 17:01:10]
  • 提交

answer

#include <bits/stdc++.h>
#include <functional>
#include <iomanip>
#include <ios>
#include <queue>
#include <utility>
#include <vector>

#define x first
#define y second

using namespace std;

typedef double ld;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;

const int maxn = 2e5 + 50;
const ll inf = 0x3f3f3f3f3f3f;
const vector<pll> dxy = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

ll n, m, k;
char maz[3090][3090];
ull dis[3090][3090];
bool vis[3090][3090];
map<pll, ll> body;
bool check(pll &p) { return p.x >= 1 && p.x <= n && p.y >= 1 && p.y <= m; };
void dij(pll st) {
  priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<>> q;
  for (auto [pi, di] : body) {
    dis[pi.x][pi.y] = k - 2 + k - di;
    if (st != pi)
      q.push({dis[pi.x][pi.y], pi});
  }
  q.push({0, st});
  dis[st.x][st.y] = 0;
  // for (ll i = 1; i <= n; i++) {
  //   for (ll j = 1; j <= m; j++) {
  //     cout << dis[i][j] << " \n"[j == m];
  //   }
  // }
  while (!q.empty()) {
    auto [d, p] = q.top();
    q.pop();
    if (vis[p.x][p.y])
      continue;
    vis[p.x][p.y] = true;

    for (auto [dx, dy] : dxy) {
      pll pi = {p.x + dx, p.y + dy};
      if (!check(pi))
        continue;
      if (dis[pi.x][pi.y] == 0)
        continue;
      if (vis[pi.x][pi.y])
        continue;

      if (body.count(pi) == 0) {
        if (dis[pi.x][pi.y] > (ull)d + 1) {
          dis[pi.x][pi.y] = d + 1;
          q.push({d + 1, pi});
        }
      } else {
        if (body[pi] <= (ull)d + 1 && dis[pi.x][pi.y] > (ull)d + 1) {
          dis[pi.x][pi.y] = d + 1;
          q.push({dis[pi.x][pi.y], pi});
        }
      }
    }
  }
}

void solve() {
  cin >> n >> m >> k;

  body.clear();

  pll st;
  for (ll i = k - 1; i >= 0; i--) {
    pll p;
    cin >> p.x >> p.y;
    if (i == k - 1) {
      st = p;
      body[p] = 0;
    } else {
      body[p] = i + 1;
    }
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> maz[i][j];
      vis[i][j] = false;
      if (maz[i][j] == '#') {
        dis[i][j] = 0;
        vis[i][j] = true;
      } else {
        dis[i][j] = inf;
      }
    }
  }

  // for (ll i = 1; i <= n; i++) {
  //   for (ll j = 1; j <= m; j++) {
  //     cout << dis[i][j] << " \n"[j == m];
  //   }
  // }

  dij(st);

  ull ans = 0;
  for (ll i = 1; i <= n; i++) {
    for (ll j = 1; j <= m; j++) {
      ull d = dis[i][j];
      if (d == inf)
        d = 0;
      ans += d * d;
      // cout << d << " \n"[j == m];
    }
  }
  cout << fixed << setprecision(0) << ans << '\n';
}

void init() {
  // init_primes();
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  int _t = 1;
  // cin >> _t;
  // cin.get();
  while (_t--)
    solve();

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 998ms
memory: 96636kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 894ms
memory: 94572kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 183ms
memory: 96804kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 141ms
memory: 96788kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 1054ms
memory: 94244kb

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: 954ms
memory: 96740kb

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: -100
Wrong Answer
time: 182ms
memory: 96508kb

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:

41915

result:

wrong answer 1st lines differ - expected: '40571', found: '41915'