oj.uz

Submission #684667

# Submission time Handle Problem Language Result Execution time Memory
684667 2023-01-22T09:36:54 Z peijar Soccer (JOI17_soccer) C++17
100 / 100
 473 ms 30688 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7252 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 269 ms 28268 KB Output is correct
4 Correct 311 ms 28348 KB Output is correct
5 Correct 42 ms 7636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 28312 KB Output is correct
2 Correct 320 ms 28336 KB Output is correct
3 Correct 226 ms 24364 KB Output is correct
4 Correct 217 ms 28312 KB Output is correct
5 Correct 258 ms 24344 KB Output is correct
6 Correct 230 ms 28328 KB Output is correct
7 Correct 342 ms 28300 KB Output is correct
8 Correct 288 ms 28352 KB Output is correct
9 Correct 336 ms 28412 KB Output is correct
10 Correct 38 ms 5720 KB Output is correct
11 Correct 338 ms 28360 KB Output is correct
12 Correct 325 ms 28364 KB Output is correct
13 Correct 167 ms 24372 KB Output is correct
14 Correct 322 ms 28384 KB Output is correct
15 Correct 262 ms 24412 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7252 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 269 ms 28268 KB Output is correct
4 Correct 311 ms 28348 KB Output is correct
5 Correct 42 ms 7636 KB Output is correct
6 Correct 322 ms 28312 KB Output is correct
7 Correct 320 ms 28336 KB Output is correct
8 Correct 226 ms 24364 KB Output is correct
9 Correct 217 ms 28312 KB Output is correct
10 Correct 258 ms 24344 KB Output is correct
11 Correct 230 ms 28328 KB Output is correct
12 Correct 342 ms 28300 KB Output is correct
13 Correct 288 ms 28352 KB Output is correct
14 Correct 336 ms 28412 KB Output is correct
15 Correct 38 ms 5720 KB Output is correct
16 Correct 338 ms 28360 KB Output is correct
17 Correct 325 ms 28364 KB Output is correct
18 Correct 167 ms 24372 KB Output is correct
19 Correct 322 ms 28384 KB Output is correct
20 Correct 262 ms 24412 KB Output is correct
21 Correct 57 ms 8016 KB Output is correct
22 Correct 413 ms 28360 KB Output is correct
23 Correct 391 ms 22232 KB Output is correct
24 Correct 436 ms 24268 KB Output is correct
25 Correct 355 ms 28400 KB Output is correct
26 Correct 354 ms 28668 KB Output is correct
27 Correct 209 ms 22012 KB Output is correct
28 Correct 188 ms 22628 KB Output is correct
29 Correct 323 ms 26484 KB Output is correct
30 Correct 170 ms 22460 KB Output is correct
31 Correct 365 ms 28340 KB Output is correct
32 Correct 473 ms 30688 KB Output is correct
33 Correct 265 ms 28380 KB Output is correct
34 Correct 448 ms 28356 KB Output is correct
35 Correct 156 ms 22464 KB Output is correct