oj.uz

Submission #814566

# Submission time Handle Problem Language Result Execution time Memory
814566 2023-08-08T08:22:02 Z kebine Tracks in the Snow (BOI13_tracks) C++17
34.375 / 100
 2000 ms 78708 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 189 ms 18876 KB Output is correct
2 Correct 126 ms 16064 KB Output is correct
3 Correct 38 ms 16192 KB Output is correct
4 Correct 29 ms 18516 KB Output is correct
5 Correct 135 ms 17448 KB Output is correct
6 Correct 124 ms 16060 KB Output is correct
7 Correct 30 ms 16084 KB Output is correct
8 Correct 11 ms 16256 KB Output is correct
9 Correct 43 ms 16340 KB Output is correct
10 Correct 165 ms 17236 KB Output is correct
11 Correct 13 ms 16852 KB Output is correct
12 Correct 80 ms 17612 KB Output is correct
13 Correct 148 ms 17448 KB Output is correct
14 Correct 141 ms 17452 KB Output is correct
15 Correct 477 ms 19028 KB Output is correct
16 Correct 213 ms 18876 KB Output is correct
17 Correct 501 ms 18836 KB Output is correct
18 Correct 29 ms 18572 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 31440 KB Time limit exceeded
2 Execution timed out 2073 ms 27112 KB Time limit exceeded
3 Execution timed out 2077 ms 78576 KB Time limit exceeded
4 Execution timed out 2074 ms 38200 KB Time limit exceeded
5 Execution timed out 2070 ms 62888 KB Time limit exceeded
6 Execution timed out 2040 ms 78612 KB Time limit exceeded
7 Execution timed out 2072 ms 32224 KB Time limit exceeded
8 Execution timed out 2055 ms 31444 KB Time limit exceeded
9 Correct 295 ms 16212 KB Output is correct
10 Execution timed out 2076 ms 16088 KB Time limit exceeded
11 Execution timed out 2091 ms 31924 KB Time limit exceeded
12 Execution timed out 2079 ms 16560 KB Time limit exceeded
13 Execution timed out 2060 ms 27112 KB Time limit exceeded
14 Execution timed out 2066 ms 23164 KB Time limit exceeded
15 Execution timed out 2054 ms 23896 KB Time limit exceeded
16 Execution timed out 2045 ms 20072 KB Time limit exceeded
17 Execution timed out 2041 ms 39996 KB Time limit exceeded
18 Execution timed out 2058 ms 39612 KB Time limit exceeded
19 Execution timed out 2017 ms 38196 KB Time limit exceeded
20 Execution timed out 2073 ms 36456 KB Time limit exceeded
21 Execution timed out 2081 ms 64516 KB Time limit exceeded
22 Execution timed out 2081 ms 62984 KB Time limit exceeded
23 Execution timed out 2072 ms 55188 KB Time limit exceeded
24 Execution timed out 2073 ms 64024 KB Time limit exceeded
25 Execution timed out 2078 ms 78604 KB Time limit exceeded
26 Correct 780 ms 70992 KB Output is correct
27 Execution timed out 2043 ms 78700 KB Time limit exceeded
28 Execution timed out 2081 ms 78704 KB Time limit exceeded
29 Execution timed out 2067 ms 78708 KB Time limit exceeded
30 Execution timed out 2072 ms 77448 KB Time limit exceeded
31 Execution timed out 2064 ms 66160 KB Time limit exceeded
32 Execution timed out 2036 ms 78708 KB Time limit exceeded