oj.uz

Submission #894218

# Submission time Handle Problem Language Result Execution time Memory
894218 2023-12-28T02:57:27 Z box Soccer (JOI17_soccer) C++17
100 / 100
 335 ms 20992 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 58 ms 10448 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 222 ms 17792 KB Output is correct
4 Correct 213 ms 17616 KB Output is correct
5 Correct 59 ms 11016 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 18892 KB Output is correct
2 Correct 230 ms 18892 KB Output is correct
3 Correct 191 ms 17868 KB Output is correct
4 Correct 211 ms 19064 KB Output is correct
5 Correct 191 ms 18376 KB Output is correct
6 Correct 214 ms 17864 KB Output is correct
7 Correct 251 ms 18608 KB Output is correct
8 Correct 267 ms 17520 KB Output is correct
9 Correct 251 ms 18932 KB Output is correct
10 Correct 42 ms 12896 KB Output is correct
11 Correct 279 ms 18156 KB Output is correct
12 Correct 241 ms 17752 KB Output is correct
13 Correct 156 ms 18372 KB Output is correct
14 Correct 238 ms 19296 KB Output is correct
15 Correct 186 ms 18480 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10448 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 222 ms 17792 KB Output is correct
4 Correct 213 ms 17616 KB Output is correct
5 Correct 59 ms 11016 KB Output is correct
6 Correct 256 ms 18892 KB Output is correct
7 Correct 230 ms 18892 KB Output is correct
8 Correct 191 ms 17868 KB Output is correct
9 Correct 211 ms 19064 KB Output is correct
10 Correct 191 ms 18376 KB Output is correct
11 Correct 214 ms 17864 KB Output is correct
12 Correct 251 ms 18608 KB Output is correct
13 Correct 267 ms 17520 KB Output is correct
14 Correct 251 ms 18932 KB Output is correct
15 Correct 42 ms 12896 KB Output is correct
16 Correct 279 ms 18156 KB Output is correct
17 Correct 241 ms 17752 KB Output is correct
18 Correct 156 ms 18372 KB Output is correct
19 Correct 238 ms 19296 KB Output is correct
20 Correct 186 ms 18480 KB Output is correct
21 Correct 72 ms 9212 KB Output is correct
22 Correct 305 ms 18248 KB Output is correct
23 Correct 269 ms 15076 KB Output is correct
24 Correct 298 ms 14632 KB Output is correct
25 Correct 258 ms 19296 KB Output is correct
26 Correct 310 ms 19004 KB Output is correct
27 Correct 203 ms 13292 KB Output is correct
28 Correct 194 ms 13656 KB Output is correct
29 Correct 269 ms 17296 KB Output is correct
30 Correct 164 ms 13420 KB Output is correct
31 Correct 262 ms 17712 KB Output is correct
32 Correct 330 ms 20992 KB Output is correct
33 Correct 223 ms 18932 KB Output is correct
34 Correct 335 ms 18424 KB Output is correct
35 Correct 158 ms 13128 KB Output is correct