oj.uz

Submission #814550

# Submission time Handle Problem Language Result Execution time Memory
814550 2023-08-08T08:18:50 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
34.375 / 100
 2000 ms 78712 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 18772 KB Output is correct
2 Correct 147 ms 16060 KB Output is correct
3 Correct 28 ms 16212 KB Output is correct
4 Correct 36 ms 18576 KB Output is correct
5 Correct 152 ms 17452 KB Output is correct
6 Correct 132 ms 16056 KB Output is correct
7 Correct 34 ms 16188 KB Output is correct
8 Correct 10 ms 16212 KB Output is correct
9 Correct 51 ms 16424 KB Output is correct
10 Correct 192 ms 17236 KB Output is correct
11 Correct 16 ms 16852 KB Output is correct
12 Correct 89 ms 17512 KB Output is correct
13 Correct 162 ms 17452 KB Output is correct
14 Correct 172 ms 17452 KB Output is correct
15 Correct 465 ms 18968 KB Output is correct
16 Correct 194 ms 18872 KB Output is correct
17 Correct 485 ms 18824 KB Output is correct
18 Correct 28 ms 18568 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 31444 KB Time limit exceeded
2 Execution timed out 2088 ms 27104 KB Time limit exceeded
3 Execution timed out 2013 ms 78632 KB Time limit exceeded
4 Execution timed out 2083 ms 38192 KB Time limit exceeded
5 Execution timed out 2086 ms 62968 KB Time limit exceeded
6 Execution timed out 2060 ms 78704 KB Time limit exceeded
7 Execution timed out 2054 ms 32212 KB Time limit exceeded
8 Execution timed out 2041 ms 31460 KB Time limit exceeded
9 Correct 376 ms 16212 KB Output is correct
10 Execution timed out 2056 ms 16084 KB Time limit exceeded
11 Execution timed out 2037 ms 31956 KB Time limit exceeded
12 Execution timed out 2061 ms 16564 KB Time limit exceeded
13 Execution timed out 2061 ms 27104 KB Time limit exceeded
14 Execution timed out 2045 ms 23244 KB Time limit exceeded
15 Execution timed out 2076 ms 23832 KB Time limit exceeded
16 Execution timed out 2082 ms 20080 KB Time limit exceeded
17 Execution timed out 2084 ms 39928 KB Time limit exceeded
18 Execution timed out 2076 ms 39600 KB Time limit exceeded
19 Execution timed out 2062 ms 38196 KB Time limit exceeded
20 Execution timed out 2079 ms 36432 KB Time limit exceeded
21 Execution timed out 2055 ms 64536 KB Time limit exceeded
22 Execution timed out 2068 ms 62996 KB Time limit exceeded
23 Execution timed out 2065 ms 55160 KB Time limit exceeded
24 Execution timed out 2045 ms 63984 KB Time limit exceeded
25 Execution timed out 2076 ms 78560 KB Time limit exceeded
26 Correct 868 ms 70876 KB Output is correct
27 Execution timed out 2049 ms 78644 KB Time limit exceeded
28 Execution timed out 2069 ms 78708 KB Time limit exceeded
29 Execution timed out 2076 ms 78712 KB Time limit exceeded
30 Execution timed out 2009 ms 77420 KB Time limit exceeded
31 Execution timed out 2037 ms 66168 KB Time limit exceeded
32 Execution timed out 2058 ms 78624 KB Time limit exceeded