oj.uz

Submission #814579

# Submission time Handle Problem Language Result Execution time Memory
814579 2023-08-08T08:25:12 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
34.375 / 100
 2000 ms 79632 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 197 ms 18888 KB Output is correct
2 Correct 170 ms 16060 KB Output is correct
3 Correct 30 ms 16212 KB Output is correct
4 Correct 33 ms 18572 KB Output is correct
5 Correct 147 ms 17452 KB Output is correct
6 Correct 124 ms 15956 KB Output is correct
7 Correct 44 ms 16084 KB Output is correct
8 Correct 13 ms 16260 KB Output is correct
9 Correct 43 ms 16340 KB Output is correct
10 Correct 212 ms 17228 KB Output is correct
11 Correct 15 ms 16852 KB Output is correct
12 Correct 76 ms 17504 KB Output is correct
13 Correct 135 ms 17460 KB Output is correct
14 Correct 172 ms 17456 KB Output is correct
15 Correct 462 ms 18964 KB Output is correct
16 Correct 235 ms 18868 KB Output is correct
17 Correct 480 ms 18832 KB Output is correct
18 Correct 29 ms 18588 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 31524 KB Time limit exceeded
2 Execution timed out 2037 ms 27108 KB Time limit exceeded
3 Execution timed out 2079 ms 79400 KB Time limit exceeded
4 Execution timed out 2015 ms 39172 KB Time limit exceeded
5 Execution timed out 2052 ms 64044 KB Time limit exceeded
6 Execution timed out 2064 ms 78832 KB Time limit exceeded
7 Execution timed out 2070 ms 32232 KB Time limit exceeded
8 Execution timed out 2076 ms 31572 KB Time limit exceeded
9 Correct 315 ms 16276 KB Output is correct
10 Execution timed out 2056 ms 16064 KB Time limit exceeded
11 Execution timed out 2079 ms 31956 KB Time limit exceeded
12 Execution timed out 2069 ms 16596 KB Time limit exceeded
13 Execution timed out 2072 ms 27364 KB Time limit exceeded
14 Execution timed out 2069 ms 23444 KB Time limit exceeded
15 Execution timed out 2080 ms 24068 KB Time limit exceeded
16 Execution timed out 2062 ms 20328 KB Time limit exceeded
17 Execution timed out 2059 ms 40908 KB Time limit exceeded
18 Execution timed out 2027 ms 40588 KB Time limit exceeded
19 Execution timed out 2017 ms 39092 KB Time limit exceeded
20 Execution timed out 2043 ms 37272 KB Time limit exceeded
21 Execution timed out 2044 ms 65648 KB Time limit exceeded
22 Execution timed out 2050 ms 64140 KB Time limit exceeded
23 Execution timed out 2021 ms 56376 KB Time limit exceeded
24 Execution timed out 2037 ms 65092 KB Time limit exceeded
25 Execution timed out 2013 ms 79632 KB Time limit exceeded
26 Correct 929 ms 71004 KB Output is correct
27 Execution timed out 2104 ms 79096 KB Time limit exceeded
28 Execution timed out 2057 ms 78972 KB Time limit exceeded
29 Execution timed out 2033 ms 79036 KB Time limit exceeded
30 Execution timed out 2048 ms 77756 KB Time limit exceeded
31 Execution timed out 2077 ms 67320 KB Time limit exceeded
32 Execution timed out 2092 ms 79000 KB Time limit exceeded