oj.uz

Submission #814581

# Submission time Handle Problem Language Result Execution time Memory
814581 2023-08-08T08:25:25 Z makanhulia Tracks in the Snow (BOI13_tracks) C++17
34.375 / 100
 2000 ms 78884 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 198 ms 19112 KB Output is correct
2 Correct 189 ms 16064 KB Output is correct
3 Correct 41 ms 16196 KB Output is correct
4 Correct 35 ms 18696 KB Output is correct
5 Correct 143 ms 17532 KB Output is correct
6 Correct 163 ms 16064 KB Output is correct
7 Correct 36 ms 16212 KB Output is correct
8 Correct 13 ms 16264 KB Output is correct
9 Correct 62 ms 16428 KB Output is correct
10 Correct 207 ms 17296 KB Output is correct
11 Correct 18 ms 16992 KB Output is correct
12 Correct 113 ms 17576 KB Output is correct
13 Correct 222 ms 17508 KB Output is correct
14 Correct 195 ms 17492 KB Output is correct
15 Correct 566 ms 19212 KB Output is correct
16 Correct 231 ms 19112 KB Output is correct
17 Correct 585 ms 19068 KB Output is correct
18 Correct 32 ms 18644 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 31568 KB Time limit exceeded
2 Execution timed out 2079 ms 27312 KB Time limit exceeded
3 Execution timed out 2033 ms 78884 KB Time limit exceeded
4 Execution timed out 2070 ms 38196 KB Time limit exceeded
5 Execution timed out 2070 ms 62888 KB Time limit exceeded
6 Execution timed out 2070 ms 78740 KB Time limit exceeded
7 Execution timed out 2084 ms 32152 KB Time limit exceeded
8 Execution timed out 2061 ms 31444 KB Time limit exceeded
9 Correct 353 ms 16220 KB Output is correct
10 Execution timed out 2079 ms 16084 KB Time limit exceeded
11 Execution timed out 2031 ms 31880 KB Time limit exceeded
12 Execution timed out 2060 ms 16640 KB Time limit exceeded
13 Execution timed out 2082 ms 27104 KB Time limit exceeded
14 Execution timed out 2061 ms 23164 KB Time limit exceeded
15 Execution timed out 2088 ms 23892 KB Time limit exceeded
16 Execution timed out 2045 ms 20052 KB Time limit exceeded
17 Execution timed out 2086 ms 39924 KB Time limit exceeded
18 Execution timed out 2061 ms 39596 KB Time limit exceeded
19 Execution timed out 2009 ms 38196 KB Time limit exceeded
20 Execution timed out 2047 ms 36472 KB Time limit exceeded
21 Execution timed out 2080 ms 64588 KB Time limit exceeded
22 Execution timed out 2063 ms 62936 KB Time limit exceeded
23 Execution timed out 2069 ms 55172 KB Time limit exceeded
24 Execution timed out 2064 ms 63916 KB Time limit exceeded
25 Execution timed out 2063 ms 78644 KB Time limit exceeded
26 Correct 917 ms 70880 KB Output is correct
27 Execution timed out 2059 ms 78712 KB Time limit exceeded
28 Execution timed out 2094 ms 78776 KB Time limit exceeded
29 Execution timed out 2089 ms 78712 KB Time limit exceeded
30 Execution timed out 2085 ms 77348 KB Time limit exceeded
31 Execution timed out 2067 ms 66164 KB Time limit exceeded
32 Execution timed out 2075 ms 78696 KB Time limit exceeded