oj.uz

Submission #881366

# Submission time Handle Problem Language Result Execution time Memory
881366 2023-12-01T07:51:57 Z MilosMilutinovic Soccer (JOI17_soccer) C++14
100 / 100
 601 ms 115016 KB 
#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;
  h += 1;
  w += 1;
  int a, b, c;
  cin >> a >> b >> c;
  int n;
  cin >> n;
  vector<int> s(n), t(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i] >> t[i];
  }
  int ver = 3 * h * w;
  auto Id = [&](int x, int y, int t) {
    return (x * w + y) * 3 + t;
  };
  vector<vector<int>> f(h, vector<int>(w, -1));
  {
    vector<pair<int, int>> que;
    for (int i = 0; i < n; i++) {
      que.emplace_back(s[i], t[i]);
      f[s[i]][t[i]] = 0;
    }
    auto Valid = [&](int x, int y) {
      return 0 <= x && x < h && 0 <= y && y < w;
    };
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b].first;
      int y = que[b].second;
      for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (Valid(nx, ny) && f[nx][ny] == -1) {
          f[nx][ny] = f[x][y] + 1;
          que.emplace_back(nx, ny);
        }
      }
    }
  }
  vector<vector<pair<int, long long>>> g(ver);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i > 0) {
        g[Id(i, j, 0)].emplace_back(Id(i - 1, j, 0), a);
        g[Id(i, j, 2)].emplace_back(Id(i - 1, j, 2), c);
      }
      if (i + 1 < h) {
        g[Id(i, j, 0)].emplace_back(Id(i + 1, j, 0), a);
        g[Id(i, j, 2)].emplace_back(Id(i + 1, j, 2), c);
      }
      if (j > 0) {
        g[Id(i, j, 1)].emplace_back(Id(i, j - 1, 1), a);
        g[Id(i, j, 2)].emplace_back(Id(i, j - 1, 2), c);
      }
      if (j + 1 < w) {
        g[Id(i, j, 1)].emplace_back(Id(i, j + 1, 1), a);
        g[Id(i, j, 2)].emplace_back(Id(i, j + 1, 2), c);
      }
      g[Id(i, j, 2)].emplace_back(Id(i, j, 0), b);
      g[Id(i, j, 2)].emplace_back(Id(i, j, 1), b);
      g[Id(i, j, 0)].emplace_back(Id(i, j, 2), f[i][j] * 1LL * c);
      g[Id(i, j, 1)].emplace_back(Id(i, j, 2), f[i][j] * 1LL * c);
    }
  }
  const long long inf = (long long) 1e18;
  vector<long long> dist(ver, inf);
  dist[Id(s[0], t[0], 2)] = 0;
  set<pair<long long, int>> st;
  st.emplace(0LL, Id(s[0], t[0], 2));
  while (!st.empty()) {
    auto it = st.begin();
    int i = it->second;
    st.erase(it);
    for (auto& p : g[i]) {
      int to = p.first;
      long long w = p.second;
      if (dist[to] > dist[i] + w) {
        if (dist[to] != inf) {
          st.erase(st.find({dist[to], to}));
        }
        dist[to] = dist[i] + w;
        st.emplace(dist[to], to);
      }
    }
  }
  long long res = dist[Id(s[n - 1], t[n - 1], 2)];
  cout << (res == inf ? -1 : res) << '\n';
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 26340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 410 ms 109012 KB Output is correct
4 Correct 454 ms 109824 KB Output is correct
5 Correct 78 ms 36836 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 112576 KB Output is correct
2 Correct 425 ms 113684 KB Output is correct
3 Correct 304 ms 89724 KB Output is correct
4 Correct 254 ms 107780 KB Output is correct
5 Correct 308 ms 89744 KB Output is correct
6 Correct 294 ms 111888 KB Output is correct
7 Correct 441 ms 114948 KB Output is correct
8 Correct 387 ms 114908 KB Output is correct
9 Correct 439 ms 114120 KB Output is correct
10 Correct 47 ms 18324 KB Output is correct
11 Correct 443 ms 115016 KB Output is correct
12 Correct 441 ms 114372 KB Output is correct
13 Correct 242 ms 90628 KB Output is correct
14 Correct 454 ms 114972 KB Output is correct
15 Correct 339 ms 91976 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 26340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 410 ms 109012 KB Output is correct
4 Correct 454 ms 109824 KB Output is correct
5 Correct 78 ms 36836 KB Output is correct
6 Correct 427 ms 112576 KB Output is correct
7 Correct 425 ms 113684 KB Output is correct
8 Correct 304 ms 89724 KB Output is correct
9 Correct 254 ms 107780 KB Output is correct
10 Correct 308 ms 89744 KB Output is correct
11 Correct 294 ms 111888 KB Output is correct
12 Correct 441 ms 114948 KB Output is correct
13 Correct 387 ms 114908 KB Output is correct
14 Correct 439 ms 114120 KB Output is correct
15 Correct 47 ms 18324 KB Output is correct
16 Correct 443 ms 115016 KB Output is correct
17 Correct 441 ms 114372 KB Output is correct
18 Correct 242 ms 90628 KB Output is correct
19 Correct 454 ms 114972 KB Output is correct
20 Correct 339 ms 91976 KB Output is correct
21 Correct 90 ms 36596 KB Output is correct
22 Correct 601 ms 107680 KB Output is correct
23 Correct 500 ms 96804 KB Output is correct
24 Correct 512 ms 104888 KB Output is correct
25 Correct 532 ms 111564 KB Output is correct
26 Correct 462 ms 108112 KB Output is correct
27 Correct 278 ms 100564 KB Output is correct
28 Correct 300 ms 101392 KB Output is correct
29 Correct 394 ms 105884 KB Output is correct
30 Correct 283 ms 101256 KB Output is correct
31 Correct 525 ms 115008 KB Output is correct
32 Correct 571 ms 114008 KB Output is correct
33 Correct 366 ms 111620 KB Output is correct
34 Correct 593 ms 111244 KB Output is correct
35 Correct 242 ms 101136 KB Output is correct