Submission #654297

#	Time	Username	Problem	Language	Result	Execution time	Memory
654297		lunchbox1	Soccer (JOI17_soccer)	C++17	100 / 100	437 ms	19068 KiB

soccer

/*
 Soccer
 https://oj.uz/problem/view/JOI17_soccer
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
 
template<class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
 
const int N = 501, K = 100000;
const LL INF = 0x3f3f3f3f3f3f3f3f;
 
int main() {
 ios::sync_with_stdio(false);
 cin.tie(NULL);
 static int xx[K], yy[K], cc[N][N];
 static LL dd[N][N][5];
 min_pq<tuple<LL, int, int, int>> pq;
 queue<pair<int, int>> qu;
 int n, m, k, a, b, c;
 LL 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, LL 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 + (LL) 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