oj.uz

Submission #814541

# Submission time Handle Problem Language Result Execution time Memory
814541 2023-08-08T08:17:17 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
34.375 / 100
 2000 ms 94340 KB 
#include <bits/stdc++.h>
using namespace std;

int h, w, total;
int meadow[4005][4005];
bool vis[4005][4005];
// vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int main() {
  cin >> h >> w;
  char in;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> in;
      if (in == '.') {
        meadow[i][j] = -1;
      } else if (in == 'R') {
        meadow[i][j] = 1;
        total++;
      }
      else {
        meadow[i][j] = 0;
        total++;
      }
    }
  }

  // for (int i = 1; i <= h; i++) {
  //   for (int j = 1; j <= w; j++) {
  //     cout << meadow[i][j] << "	";
  //   }
  //   cout << endl;
  // }
  int ans = 0;

  while (true) {
    queue<pair<int, int>> q;
    memset(vis, 0, sizeof(vis));

    q.push({1, 1});
    vis[1][1] = 1;
    int row, col, count = 1;
    int top = meadow[1][1];
    meadow[1][1] += 1;
    meadow[1][1] %= 2;
    ans++;

    while (!q.empty()) {
      row = q.front().first;
      col = q.front().second;
      q.pop();

      for (int i = 0; i < 4; i++) {
        if (row + dir[i][0] > 0 and row + dir[i][0] <= h and col + dir[i][1] > 0 and col + dir[i][1] <= w and !vis[row+dir[i][0]][col+dir[i][1]] and meadow[row+dir[i][0]][col+dir[i][1]] == top) {
          q.push({row+dir[i][0], col+dir[i][1]});
          meadow[row+dir[i][0]][col+dir[i][1]] += 1;
          meadow[row+dir[i][0]][col+dir[i][1]] %= 2;
          vis[row+dir[i][0]][col+dir[i][1]] = 1;
          count++;
        }
      }
    }

    // for (int i = 1; i <= h; i++) {
    //   for (int j = 1; j <= w; j++) {
    //     cout << meadow[i][j] << "	";
    //   }
    //   cout << endl;
    // }
    // cout << count << " " << total << endl;
    // cout << endl;

    // break;



    if (count == total) {
      cout << ans << endl;
      return 0;
    }
  }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 19112 KB Output is correct
2 Correct 161 ms 16060 KB Output is correct
3 Correct 42 ms 16192 KB Output is correct
4 Correct 33 ms 18700 KB Output is correct
5 Correct 134 ms 17536 KB Output is correct
6 Correct 161 ms 16060 KB Output is correct
7 Correct 29 ms 16212 KB Output is correct
8 Correct 14 ms 16212 KB Output is correct
9 Correct 39 ms 16432 KB Output is correct
10 Correct 171 ms 17288 KB Output is correct
11 Correct 13 ms 16980 KB Output is correct
12 Correct 75 ms 17576 KB Output is correct
13 Correct 133 ms 17536 KB Output is correct
14 Correct 131 ms 17472 KB Output is correct
15 Correct 488 ms 19212 KB Output is correct
16 Correct 179 ms 19112 KB Output is correct
17 Correct 472 ms 19076 KB Output is correct
18 Correct 36 ms 18628 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 31564 KB Time limit exceeded
2 Execution timed out 2074 ms 28636 KB Time limit exceeded
3 Execution timed out 2056 ms 81188 KB Time limit exceeded
4 Execution timed out 2040 ms 41220 KB Time limit exceeded
5 Execution timed out 2044 ms 66120 KB Time limit exceeded
6 Execution timed out 2085 ms 94340 KB Time limit exceeded
7 Execution timed out 2095 ms 32212 KB Time limit exceeded
8 Execution timed out 2043 ms 31484 KB Time limit exceeded
9 Correct 400 ms 16276 KB Output is correct
10 Execution timed out 2071 ms 16084 KB Time limit exceeded
11 Execution timed out 2073 ms 31980 KB Time limit exceeded
12 Execution timed out 2081 ms 16596 KB Time limit exceeded
13 Execution timed out 2075 ms 28632 KB Time limit exceeded
14 Execution timed out 2079 ms 24048 KB Time limit exceeded
15 Execution timed out 2085 ms 24764 KB Time limit exceeded
16 Execution timed out 2074 ms 20700 KB Time limit exceeded
17 Execution timed out 2075 ms 43000 KB Time limit exceeded
18 Execution timed out 2069 ms 42800 KB Time limit exceeded
19 Execution timed out 2073 ms 41220 KB Time limit exceeded
20 Execution timed out 2085 ms 39120 KB Time limit exceeded
21 Execution timed out 2009 ms 67740 KB Time limit exceeded
22 Execution timed out 2068 ms 66092 KB Time limit exceeded
23 Execution timed out 2032 ms 58372 KB Time limit exceeded
24 Execution timed out 2083 ms 67172 KB Time limit exceeded
25 Execution timed out 2041 ms 81224 KB Time limit exceeded
26 Correct 799 ms 82844 KB Output is correct
27 Execution timed out 2047 ms 93044 KB Time limit exceeded
28 Execution timed out 2016 ms 89720 KB Time limit exceeded
29 Execution timed out 2031 ms 83480 KB Time limit exceeded
30 Execution timed out 2092 ms 86464 KB Time limit exceeded
31 Execution timed out 2031 ms 69368 KB Time limit exceeded
32 Execution timed out 2009 ms 81300 KB Time limit exceeded