oj.uz

Submission #814552

# Submission time Handle Problem Language Result Execution time Memory
814552 2023-08-08T08:18:58 Z makanhulia 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 202 ms 18892 KB Output is correct
2 Correct 188 ms 16056 KB Output is correct
3 Correct 37 ms 16192 KB Output is correct
4 Correct 28 ms 18568 KB Output is correct
5 Correct 159 ms 17448 KB Output is correct
6 Correct 129 ms 16064 KB Output is correct
7 Correct 40 ms 16084 KB Output is correct
8 Correct 12 ms 16268 KB Output is correct
9 Correct 45 ms 16424 KB Output is correct
10 Correct 240 ms 17236 KB Output is correct
11 Correct 20 ms 16880 KB Output is correct
12 Correct 84 ms 17492 KB Output is correct
13 Correct 196 ms 17452 KB Output is correct
14 Correct 167 ms 17460 KB Output is correct
15 Correct 537 ms 18968 KB Output is correct
16 Correct 223 ms 18876 KB Output is correct
17 Correct 521 ms 18828 KB Output is correct
18 Correct 30 ms 18556 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 31492 KB Time limit exceeded
2 Execution timed out 2077 ms 27048 KB Time limit exceeded
3 Execution timed out 2075 ms 78664 KB Time limit exceeded
4 Execution timed out 2083 ms 38192 KB Time limit exceeded
5 Execution timed out 2085 ms 63104 KB Time limit exceeded
6 Execution timed out 2058 ms 78656 KB Time limit exceeded
7 Execution timed out 2066 ms 32212 KB Time limit exceeded
8 Execution timed out 2059 ms 31444 KB Time limit exceeded
9 Correct 349 ms 16212 KB Output is correct
10 Execution timed out 2035 ms 16008 KB Time limit exceeded
11 Execution timed out 2054 ms 31932 KB Time limit exceeded
12 Execution timed out 2061 ms 16596 KB Time limit exceeded
13 Execution timed out 2073 ms 27108 KB Time limit exceeded
14 Execution timed out 2062 ms 23160 KB Time limit exceeded
15 Execution timed out 2068 ms 23912 KB Time limit exceeded
16 Execution timed out 2073 ms 20072 KB Time limit exceeded
17 Execution timed out 2072 ms 39924 KB Time limit exceeded
18 Execution timed out 2081 ms 39608 KB Time limit exceeded
19 Execution timed out 2094 ms 38200 KB Time limit exceeded
20 Execution timed out 2072 ms 36460 KB Time limit exceeded
21 Execution timed out 2083 ms 64540 KB Time limit exceeded
22 Execution timed out 2066 ms 62976 KB Time limit exceeded
23 Execution timed out 2068 ms 55164 KB Time limit exceeded
24 Execution timed out 2059 ms 64040 KB Time limit exceeded
25 Execution timed out 2059 ms 78600 KB Time limit exceeded
26 Correct 921 ms 70968 KB Output is correct
27 Execution timed out 2073 ms 78704 KB Time limit exceeded
28 Execution timed out 2078 ms 78628 KB Time limit exceeded
29 Execution timed out 2037 ms 78708 KB Time limit exceeded
30 Execution timed out 2037 ms 77432 KB Time limit exceeded
31 Execution timed out 2024 ms 66164 KB Time limit exceeded
32 Execution timed out 2068 ms 78688 KB Time limit exceeded