oj.uz

Submission #1012939

# Submission time Handle Problem Language Result Execution time Memory
1012939 2024-07-02T22:18:13 Z parentoni Tracks in the Snow (BOI13_tracks) C++17
9.89583 / 100
 323 ms 163936 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define print(x) for (auto el: x) cout << el << " "; cout << '\n'

using ll = long long;
using llb = long double;
using vl = vector<ll>;
using pll = pair<ll,ll>;

// functions
void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }

// geometry
const double PI = 3.14159265358979323846;
double DEG_to_RAD (double d) {return d*PI/180.0;}
double RAD_to_DEG (double r) {return r*180.0/ PI;}

// values
const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MAX_N = 4000;
ll h, w;

ll dx[4] = {1,-1,0,0};
ll dy[4] = {0,0,1,-1};

vector<vector<bool>> board; // 0 if F, 1 if R;
vector<vector<bool>> visited; 
vector<vl> adj;


deque<pair<pll, ll>> q;


ll bfs() {

  q.push_back({{1,1}, 1});
  visited[1][1] = true;
  ll ans = 1;

  while(!q.empty()) {
    ans = max(ans, q.front().second);

    pll cord = q.front().first;
    //cout << cord.first << " " << cord.second << " " << q.front().second<< endl;
    q.pop_front();
    for (int i=0;i<4;i++) {
      if (visited[cord.first + dx[i]][cord.second + dy[i]]) continue;

      if (board[cord.first + dx[i]][cord.second + dy[i]] != board[cord.first][cord.second]) {
        q.push_back({{cord.first+dx[i], cord.second+dy[i]}, q.front().second+1});
      } else {
        q.push_front({{cord.first+dx[i], cord.second+dy[i]}, q.front().second});
      }

      visited[cord.first + dx[i]][cord.second + dy[i]] = true;
    }
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> h >> w; board.resize(h+2); visited.resize(h+2);
  for (auto &el: board) el.resize(w+2);
  for (auto &el: visited) el.resize(w+2);
 
  fill(visited[0].begin(),visited[0].end(), 1);
  for (int i=0;i<=h+1;i++) {visited[i][0] = true; visited[i][w+1] = true;} 
  fill(visited[h+1].begin(), visited[h+1].end(), 1);

  for (int i=1;i<=h;i++) {
    string t; cin >> t;
    for (int j=1;j<=w;j++) {
      board[i][j] = t[j] == 'F'?1:0;
      visited[i][j] = t[j] == '.'?1:0;
    }
  }

  cout << bfs() << "\n";

}

Compilation message

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:13:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:13:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1112 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 4 ms 1116 KB Output isn't correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Correct 1 ms 344 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Correct 1 ms 604 KB Output is correct
12 Incorrect 3 ms 600 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Incorrect 5 ms 828 KB Output isn't correct
16 Incorrect 6 ms 816 KB Output isn't correct
17 Incorrect 4 ms 860 KB Output isn't correct
18 Incorrect 3 ms 1112 KB Output isn't correct

Subtask #2
6.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Incorrect 20 ms 2592 KB Output isn't correct
3 Incorrect 130 ms 20564 KB Output isn't correct
4 Incorrect 35 ms 5200 KB Output isn't correct
5 Incorrect 29 ms 11600 KB Output isn't correct
6 Correct 323 ms 61724 KB Output is correct
7 Incorrect 1 ms 1116 KB Output isn't correct
8 Incorrect 1 ms 1068 KB Output isn't correct
9 Incorrect 2 ms 604 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 1 ms 976 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 22 ms 2600 KB Output isn't correct
14 Incorrect 12 ms 1628 KB Output isn't correct
15 Incorrect 5 ms 1628 KB Output isn't correct
16 Incorrect 11 ms 1116 KB Output isn't correct
17 Incorrect 56 ms 5548 KB Output isn't correct
18 Incorrect 19 ms 5464 KB Output isn't correct
19 Incorrect 32 ms 5208 KB Output isn't correct
20 Incorrect 32 ms 4700 KB Output isn't correct
21 Incorrect 80 ms 11996 KB Output isn't correct
22 Incorrect 36 ms 11600 KB Output isn't correct
23 Incorrect 114 ms 10292 KB Output isn't correct
24 Incorrect 40 ms 11864 KB Output isn't correct
25 Incorrect 150 ms 20292 KB Output isn't correct
26 Correct 254 ms 163936 KB Output is correct
27 Incorrect 263 ms 99036 KB Output isn't correct
28 Correct 303 ms 61632 KB Output is correct
29 Incorrect 306 ms 60544 KB Output isn't correct
30 Incorrect 289 ms 73068 KB Output isn't correct
31 Incorrect 276 ms 15024 KB Output isn't correct
32 Incorrect 225 ms 65604 KB Output isn't correct