oj.uz

Submission #814588

# Submission time Handle Problem Language Result Execution time Memory
814588 2023-08-08T08:27:48 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
34.375 / 100
 2000 ms 78728 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 219 ms 18880 KB Output is correct
2 Correct 132 ms 16056 KB Output is correct
3 Correct 43 ms 16084 KB Output is correct
4 Correct 32 ms 18564 KB Output is correct
5 Correct 178 ms 17452 KB Output is correct
6 Correct 159 ms 16060 KB Output is correct
7 Correct 46 ms 16212 KB Output is correct
8 Correct 12 ms 16212 KB Output is correct
9 Correct 57 ms 16424 KB Output is correct
10 Correct 237 ms 17228 KB Output is correct
11 Correct 15 ms 16952 KB Output is correct
12 Correct 102 ms 17504 KB Output is correct
13 Correct 164 ms 17364 KB Output is correct
14 Correct 166 ms 17452 KB Output is correct
15 Correct 492 ms 18964 KB Output is correct
16 Correct 210 ms 18880 KB Output is correct
17 Correct 500 ms 18832 KB Output is correct
18 Correct 28 ms 18548 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 31440 KB Time limit exceeded
2 Execution timed out 2073 ms 27108 KB Time limit exceeded
3 Execution timed out 2066 ms 78580 KB Time limit exceeded
4 Execution timed out 2073 ms 38196 KB Time limit exceeded
5 Execution timed out 2095 ms 62924 KB Time limit exceeded
6 Execution timed out 2089 ms 78728 KB Time limit exceeded
7 Execution timed out 2079 ms 32212 KB Time limit exceeded
8 Execution timed out 2070 ms 31432 KB Time limit exceeded
9 Correct 288 ms 16212 KB Output is correct
10 Execution timed out 2094 ms 16084 KB Time limit exceeded
11 Execution timed out 2080 ms 31876 KB Time limit exceeded
12 Execution timed out 2078 ms 16652 KB Time limit exceeded
13 Execution timed out 2083 ms 27104 KB Time limit exceeded
14 Execution timed out 2083 ms 23116 KB Time limit exceeded
15 Execution timed out 2080 ms 23788 KB Time limit exceeded
16 Execution timed out 2092 ms 20036 KB Time limit exceeded
17 Execution timed out 2090 ms 39916 KB Time limit exceeded
18 Execution timed out 2071 ms 39580 KB Time limit exceeded
19 Execution timed out 2045 ms 38200 KB Time limit exceeded
20 Execution timed out 2037 ms 36368 KB Time limit exceeded
21 Execution timed out 2057 ms 64604 KB Time limit exceeded
22 Execution timed out 2080 ms 62960 KB Time limit exceeded
23 Execution timed out 2070 ms 55168 KB Time limit exceeded
24 Execution timed out 2067 ms 63912 KB Time limit exceeded
25 Execution timed out 2073 ms 78636 KB Time limit exceeded
26 Correct 920 ms 70876 KB Output is correct
27 Execution timed out 2070 ms 78708 KB Time limit exceeded
28 Execution timed out 2048 ms 78612 KB Time limit exceeded
29 Execution timed out 2074 ms 78696 KB Time limit exceeded
30 Execution timed out 2055 ms 77488 KB Time limit exceeded
31 Execution timed out 2090 ms 66164 KB Time limit exceeded
32 Execution timed out 2080 ms 78700 KB Time limit exceeded