oj.uz

Submission #807676

# Submission time Handle Problem Language Result Execution time Memory
807676 2023-08-04T21:25:38 Z dong_liu Soccer (JOI17_soccer) C++17
100 / 100
 371 ms 19088 KB 
#include <bits/stdc++.h>
using namespace std;

#define sz(v) static_cast<int>((v).size())
#define long long long

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

#ifdef LOCAL
#define dbg(...) \
  printf("\033[1;34m% 4d \033[32m|\033[0m ", __LINE__), printf(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

const int N = 501, K = 100000;
const long INF = 0x3f3f3f3f3f3f3f3f;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  static int xx[K], yy[K], cc[N][N];
  static long dd[N][N][5];
  min_pq<tuple<long, int, int, int>> pq;
  queue<pair<int, int>> qu;
  int n, m, k, a, b, c;
  long ans;

  auto ad_qu = [&](int x, int y, int d) {
    if (x >= 0 && x < n && y >= 0 && y < m && cc[x][y] == -1) {
      cc[x][y] = d;
      qu.push({x, y});
    }
  };
  auto ad_pq = [&](int x, int y, int t, long d) {
    if (x >= 0 && x < n && y >= 0 && y < m && dd[x][y][t] > d) {
      dd[x][y][t] = d;
      pq.push({d, x, y, t});
    }
  };

  cin >> n >> m, n++, m++;
  cin >> a >> b >> c;
  cin >> k;
  for (int i = 0; i < k; i++) cin >> xx[i] >> yy[i];
  for (int i = 0; i < n; i++) fill(cc[i], cc[i] + m, -1);
  for (int i = 0; i < k - 1; i++) ad_qu(xx[i], yy[i], 0);
  while (!qu.empty()) {
    auto [x, y] = qu.front();

    qu.pop();
    ad_qu(x + 1, y, cc[x][y] + 1);
    ad_qu(x - 1, y, cc[x][y] + 1);
    ad_qu(x, y + 1, cc[x][y] + 1);
    ad_qu(x, y - 1, cc[x][y] + 1);
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) fill(dd[i][j], dd[i][j] + 5, INF);
  ad_pq(xx[0], yy[0], 0, 0);
  while (!pq.empty()) {
    auto [d, x, y, t] = pq.top();

    pq.pop();
    if (dd[x][y][t] != d) continue;
    if (t == 0) {
      ad_pq(x, y, 1, d + b);
      ad_pq(x, y, 2, d + b);
      ad_pq(x, y, 3, d + b);
      ad_pq(x, y, 4, d + b);
      ad_pq(x - 1, y, 0, d + c);
      ad_pq(x + 1, y, 0, d + c);
      ad_pq(x, y + 1, 0, d + c);
      ad_pq(x, y - 1, 0, d + c);
    } else {
      ad_pq(x, y, 0, d + (long)c * cc[x][y]);
      if (t == 1)
        ad_pq(x + 1, y, 1, d + a);
      else if (t == 2)
        ad_pq(x - 1, y, 2, d + a);
      else if (t == 3)
        ad_pq(x, y + 1, 3, d + a);
      else
        ad_pq(x, y - 1, 4, d + a);
    }
  }
  ans = INF;
  for (int i = 0; i <= 4; i++) ans = min(ans, dd[xx[k - 1]][yy[k - 1]][i]);
  printf("%lld\n", ans);
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6092 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 215 ms 17336 KB Output is correct
4 Correct 217 ms 17352 KB Output is correct
5 Correct 61 ms 6132 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 17348 KB Output is correct
2 Correct 235 ms 17360 KB Output is correct
3 Correct 213 ms 15344 KB Output is correct
4 Correct 207 ms 17416 KB Output is correct
5 Correct 219 ms 17428 KB Output is correct
6 Correct 243 ms 17428 KB Output is correct
7 Correct 312 ms 17536 KB Output is correct
8 Correct 259 ms 17444 KB Output is correct
9 Correct 304 ms 17488 KB Output is correct
10 Correct 40 ms 6628 KB Output is correct
11 Correct 296 ms 17544 KB Output is correct
12 Correct 311 ms 17480 KB Output is correct
13 Correct 201 ms 15268 KB Output is correct
14 Correct 325 ms 17560 KB Output is correct
15 Correct 197 ms 17524 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6092 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 215 ms 17336 KB Output is correct
4 Correct 217 ms 17352 KB Output is correct
5 Correct 61 ms 6132 KB Output is correct
6 Correct 255 ms 17348 KB Output is correct
7 Correct 235 ms 17360 KB Output is correct
8 Correct 213 ms 15344 KB Output is correct
9 Correct 207 ms 17416 KB Output is correct
10 Correct 219 ms 17428 KB Output is correct
11 Correct 243 ms 17428 KB Output is correct
12 Correct 312 ms 17536 KB Output is correct
13 Correct 259 ms 17444 KB Output is correct
14 Correct 304 ms 17488 KB Output is correct
15 Correct 40 ms 6628 KB Output is correct
16 Correct 296 ms 17544 KB Output is correct
17 Correct 311 ms 17480 KB Output is correct
18 Correct 201 ms 15268 KB Output is correct
19 Correct 325 ms 17560 KB Output is correct
20 Correct 197 ms 17524 KB Output is correct
21 Correct 67 ms 6172 KB Output is correct
22 Correct 335 ms 17424 KB Output is correct
23 Correct 278 ms 13272 KB Output is correct
24 Correct 371 ms 14500 KB Output is correct
25 Correct 290 ms 17428 KB Output is correct
26 Correct 318 ms 17592 KB Output is correct
27 Correct 217 ms 13172 KB Output is correct
28 Correct 216 ms 13780 KB Output is correct
29 Correct 300 ms 16148 KB Output is correct
30 Correct 182 ms 13292 KB Output is correct
31 Correct 369 ms 17592 KB Output is correct
32 Correct 349 ms 19088 KB Output is correct
33 Correct 232 ms 17340 KB Output is correct
34 Correct 364 ms 17612 KB Output is correct
35 Correct 167 ms 13120 KB Output is correct