Submission #684667

#	Time	Username	Problem	Language	Result	Execution time	Memory
684667		peijar	Soccer (JOI17_soccer)	C++17	100 / 100	473 ms	30688 KiB

soccer

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const pair<int, int> DELTAS[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

struct Etat {
  int lig, col, dir, dis;

  bool operator<(Etat other) const { return dis > other.dis; }
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbLig, nbCol;
  cin >> nbLig >> nbCol;
  nbLig++, nbCol++;

  int A, B, C;
  cin >> A >> B >> C;

  int nbJoueurs;
  cin >> nbJoueurs;

  vector<vector<int>> closest(nbLig, vector<int>(nbCol, -1));
  vector<pair<int, int>> posJoueurs(nbJoueurs);
  queue<pair<int, int>> q;
  for (int i = 0; i < nbJoueurs; ++i) {
    auto &[lig, col] = posJoueurs[i];
    cin >> lig >> col;
    if (closest[lig][col] == -1) {
      closest[lig][col] = 0;
      q.emplace(lig, col);
    }
  }

  dbg(closest);

  auto isSafe = [&](int lig, int col) {
    return lig >= 0 and lig < nbLig and col >= 0 and col < nbCol;
  };

  while (!q.empty()) {
    auto [lig, col] = q.front();
    q.pop();
    for (auto [dlig, dcol] : DELTAS) {
      if (isSafe(lig + dlig, col + dcol) and
          closest[lig + dlig][col + dcol] == -1) {
        closest[lig + dlig][col + dcol] = closest[lig][col] + 1;
        q.emplace(lig + dlig, col + dcol);
      }
    }
  }

  priority_queue<Etat> pq;

  pq.push({posJoueurs[0].first, posJoueurs[0].second, 4, 0});
  vector<vector<vector<int>>> dis(
      nbLig, vector<vector<int>>(nbCol, vector<int>(5, 1e18)));
  dis[posJoueurs[0].first][posJoueurs[0].second][4] = 0;

  while (!pq.empty()) {
    auto [lig, col, dir, d] = pq.top();
    pq.pop();
    if (d > dis[lig][col][dir])
      continue;

    if (dir == 4) {
      for (auto [dlig, dcol] : DELTAS) {
        if (!isSafe(lig + dlig, col + dcol))
          continue;

        int nxtDis = C + d;
        if (dis[lig + dlig][col + dcol][4] > nxtDis) {
          dis[lig + dlig][col + dcol][4] = nxtDis;
          pq.push({lig + dlig, col + dcol, 4, nxtDis});
        }
      }
      for (int i = 0; i < 4; ++i) {
        int nxtDis = B + d;
        if (dis[lig][col][i] > nxtDis) {
          dis[lig][col][i] = nxtDis;
          pq.push({lig, col, i, nxtDis});
        }
      }
    } else {
      int nxtDis = d + closest[lig][col] * C;
      if (dis[lig][col][4] > nxtDis) {
        dis[lig][col][4] = nxtDis;
        pq.push({lig, col, 4, nxtDis});
      }
      auto [dlig, dcol] = DELTAS[dir];
      nxtDis = d + A;
      if (isSafe(lig + dlig, col + dcol) and
          nxtDis < dis[lig + dlig][col + dcol][dir]) {
        dis[lig + dlig][col + dcol][dir] = nxtDis;
        pq.push({lig + dlig, col + dcol, dir, nxtDis});
      }
    }
  }

  auto [lig, col] = posJoueurs[nbJoueurs - 1];
  cout << dis[lig][col][4] << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65