Submission #651517

#	Time	Username	Problem	Language	Result	Execution time	Memory
651517		lunchbox	Soccer (JOI17_soccer)	C++17	100 / 100	457 ms	19044 KiB

soccer

/*
author: lunchbox
problem link: https://oj.uz/problem/submit/JOI17_soccer
*/
#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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65