Submission #1194109

#TimeUsernameProblemLanguageResultExecution timeMemory
1194109anastasiskolioMecho (IOI09_mecho)C++20
11 / 100
165 ms6412 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <queue> #include <array> #define MAXN 800 #define INF 1000000 using namespace std; int N, S; int Si, Sj, Ti, Tj; vector<vector<char>> A(MAXN, vector<char>(MAXN)); vector<vector<int>> Db(MAXN, vector<int>(MAXN)); // time bees arrive vector<vector<int>> Dm(MAXN, vector<int>(MAXN)); // time Mecho arrives queue<pair<int, int>> Qb; queue<array<int, 3>> Qm; // i, j, scent left void BeesGoTo(int i, int j, int D) { if (i >= 0 && i < N && j >= 0 && j < N && A[i][j] != 'T' && A[i][j] != 'D' && Db[i][j] == INF) { Db[i][j] = D + 1; Qb.push({ i, j }); } } void BeesBreadthFirstSearch() { while (!Qb.empty()) { int i = Qb.front().first; int j = Qb.front().second; Qb.pop(); BeesGoTo(i + 1, j, Db[i][j]); BeesGoTo(i - 1, j, Db[i][j]); BeesGoTo(i, j + 1, Db[i][j]); BeesGoTo(i, j - 1, Db[i][j]); } } void MechoGoTo(int i, int j, int s, int D) { if (i < 0 || i >= N || j < 0 || j >= N) return; if (A[i][j] == 'T' || A[i][j] == 'H') return; if (Dm[i][j] != INF) return; int new_time = D + (s ==0); if (new_time < Db[i][j]) { Dm[i][j] = new_time; int new_scent = (s > 0) ? s - 1 : S; Qm.push({ i, j, new_scent }); } } bool MechoBreadthFirstSearch(int start_time) { for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) Dm[i][j] = INF; Qm = queue<array<int, 3>>(); Dm[Si][Sj] = start_time; Qm.push({ Si, Sj, S }); while (!Qm.empty()) { int i = Qm.front()[0]; int j = Qm.front()[1]; int s = Qm.front()[2]; Qm.pop(); MechoGoTo(i + 1, j, s, Dm[i][j]); MechoGoTo(i - 1, j, s, Dm[i][j]); MechoGoTo(i, j + 1, s, Dm[i][j]); MechoGoTo(i, j - 1, s, Dm[i][j]); } return Dm[Ti][Tj] != INF; } int main() { scanf("%d %d", &N, &S); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { Db[i][j] = INF; scanf(" %c", &A[i][j]); if (A[i][j] == 'H') { Db[i][j] = 0; Qb.push({ i, j }); } else if (A[i][j] == 'M') { Si = i; Sj = j; } else if (A[i][j] == 'D') { Ti = i; Tj = j; } } } BeesBreadthFirstSearch(); int lo = 0, hi = N * N; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (MechoBreadthFirstSearch(mid)) lo = mid; else hi = mid - 1; } printf("%d\n", lo); return 0; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d %d", &N, &S);
      |     ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |             scanf(" %c", &A[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...