oj.uz

Submission #1012940

# Submission time Handle Problem Language Result Execution time Memory
1012940 2024-07-02T22:21:17 Z parentoni Tracks in the Snow (BOI13_tracks) C++17
51.1458 / 100
 336 ms 152076 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; ll sc = q.front().second;
    //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]}, sc+1});
      } else {
        q.push_front({{cord.first+dx[i], cord.second+dy[i]}, sc});
      }

      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
18.3333333333 / 30.0

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

Subtask #2
32.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 856 KB Output isn't correct
2 Incorrect 21 ms 860 KB Output isn't correct
3 Correct 129 ms 4928 KB Output is correct
4 Correct 30 ms 1624 KB Output is correct
5 Incorrect 23 ms 2908 KB Output isn't correct
6 Correct 318 ms 46064 KB Output is correct
7 Incorrect 1 ms 856 KB Output isn't correct
8 Incorrect 1 ms 856 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 1 ms 860 KB Output isn't correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 21 ms 1072 KB Output isn't correct
14 Incorrect 12 ms 856 KB Output isn't correct
15 Incorrect 4 ms 604 KB Output isn't correct
16 Correct 13 ms 688 KB Output is correct
17 Correct 55 ms 1628 KB Output is correct
18 Incorrect 17 ms 1712 KB Output isn't correct
19 Correct 30 ms 1652 KB Output is correct
20 Correct 31 ms 1528 KB Output is correct
21 Incorrect 76 ms 2908 KB Output isn't correct
22 Incorrect 23 ms 2908 KB Output isn't correct
23 Incorrect 120 ms 2640 KB Output isn't correct
24 Incorrect 35 ms 3072 KB Output isn't correct
25 Correct 152 ms 4696 KB Output is correct
26 Correct 268 ms 152076 KB Output is correct
27 Correct 278 ms 83416 KB Output is correct
28 Correct 336 ms 46016 KB Output is correct
29 Incorrect 281 ms 45196 KB Output isn't correct
30 Correct 291 ms 57596 KB Output is correct
31 Incorrect 291 ms 5000 KB Output isn't correct
32 Incorrect 240 ms 50132 KB Output isn't correct