oj.uz

Submission #814559

# Submission time Handle Problem Language Result Execution time Memory
814559 2023-08-08T08:20:34 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
34.375 / 100
 2000 ms 78808 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 195 ms 18872 KB Output is correct
2 Correct 154 ms 16060 KB Output is correct
3 Correct 28 ms 16084 KB Output is correct
4 Correct 28 ms 18516 KB Output is correct
5 Correct 159 ms 17464 KB Output is correct
6 Correct 136 ms 16072 KB Output is correct
7 Correct 36 ms 16084 KB Output is correct
8 Correct 11 ms 16160 KB Output is correct
9 Correct 38 ms 16440 KB Output is correct
10 Correct 177 ms 17236 KB Output is correct
11 Correct 14 ms 16852 KB Output is correct
12 Correct 75 ms 17492 KB Output is correct
13 Correct 141 ms 17456 KB Output is correct
14 Correct 138 ms 17460 KB Output is correct
15 Correct 475 ms 18964 KB Output is correct
16 Correct 202 ms 18876 KB Output is correct
17 Correct 478 ms 18824 KB Output is correct
18 Correct 29 ms 18516 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 31484 KB Time limit exceeded
2 Execution timed out 2064 ms 27120 KB Time limit exceeded
3 Execution timed out 2077 ms 78580 KB Time limit exceeded
4 Execution timed out 2080 ms 38196 KB Time limit exceeded
5 Execution timed out 2076 ms 62984 KB Time limit exceeded
6 Execution timed out 2074 ms 78704 KB Time limit exceeded
7 Execution timed out 2065 ms 32212 KB Time limit exceeded
8 Execution timed out 2056 ms 31444 KB Time limit exceeded
9 Correct 278 ms 16212 KB Output is correct
10 Execution timed out 2068 ms 16084 KB Time limit exceeded
11 Execution timed out 2049 ms 31956 KB Time limit exceeded
12 Execution timed out 2052 ms 16596 KB Time limit exceeded
13 Execution timed out 2068 ms 27036 KB Time limit exceeded
14 Execution timed out 2083 ms 23164 KB Time limit exceeded
15 Execution timed out 2058 ms 23884 KB Time limit exceeded
16 Execution timed out 2069 ms 20076 KB Time limit exceeded
17 Execution timed out 2066 ms 39888 KB Time limit exceeded
18 Execution timed out 2068 ms 39532 KB Time limit exceeded
19 Execution timed out 2071 ms 38176 KB Time limit exceeded
20 Execution timed out 2082 ms 36388 KB Time limit exceeded
21 Execution timed out 2082 ms 64564 KB Time limit exceeded
22 Execution timed out 2080 ms 62876 KB Time limit exceeded
23 Execution timed out 2059 ms 55168 KB Time limit exceeded
24 Execution timed out 2087 ms 64020 KB Time limit exceeded
25 Execution timed out 2071 ms 78564 KB Time limit exceeded
26 Correct 866 ms 70872 KB Output is correct
27 Execution timed out 2057 ms 78708 KB Time limit exceeded
28 Execution timed out 2084 ms 78712 KB Time limit exceeded
29 Execution timed out 2090 ms 78808 KB Time limit exceeded
30 Execution timed out 2095 ms 77436 KB Time limit exceeded
31 Execution timed out 2080 ms 66204 KB Time limit exceeded
32 Execution timed out 2086 ms 78660 KB Time limit exceeded