oj.uz

Submission #1094850

# Submission time Handle Problem Language Result Execution time Memory
1094850 2024-09-30T16:38:26 Z wrtt Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 693 ms 222212 KB 
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define pb emplace_back
#define mx(a, b) ((a) > (b) ? (a) : (b))
#define mn(a, b) ((a) < (b) ? (a) : (b))
#define graph(n) vector<int> g[(n)+1];
constexpr int mod = 1000000007;

void frx(std::string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}

/*
template <typename T, size_t N>
std::ostream &operator<<(std::ostream &os, const T (&arr)[N]) {
  os << "[";
  for(size_t i = 0; i < N; ++i) {
    if(i>0) {
      os << ", ";
    }
    os<<arr[i];
  }
  return os << "]";
}
*/
int h,w;
char a[4001][4001];

bool is(int i, int j) {
  return i>=0 && i<h && j>=0 && j<w && a[i][j]!='.';
}


void solve() {
  cin >> h >> w;
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      cin>>a[i][j];
    }
  }
  int dist[h][w];
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      dist[i][j] = 1e18;
    }
  }
  dist[0][0] = 1;
  deque<pair<int,int>> q;
  q.push_front({0,0});
  int ans = 0;
  while(!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop_front();
    ans=mx(ans, dist[x][y]);
    if(is(x-1,y)) {
      if(dist[x-1][y] >dist[x][y]+(a[x][y] != a[x-1][y])) {
        dist[x-1][y] = dist[x][y]+(a[x][y] != a[x-1][y]);
        if(a[x][y] != a[x-1][y]) {
          q.push_back({x-1,y});
        } else {
          q.push_front({x-1,y});
        }
      } 
    }
    if(is(x+1,y)) {
      if(dist[x+1][y] > dist[x][y]+(a[x][y] != a[x+1][y])) {
        dist[x+1][y] = dist[x][y]+(a[x][y] != a[x+1][y]);
        if(a[x][y] != a[x+1][y]) {
          q.push_back({x+1,y});
        } else {
          q.push_front({x+1,y});
        }
      } 
    }
    if(is(x,y-1)) {
      if(dist[x][y-1] > dist[x][y]+(a[x][y] != a[x][y-1])) {
        dist[x][y-1] = dist[x][y]+(a[x][y] != a[x][y-1]);
        if(a[x][y] != a[x][y-1]) {
          q.push_back({x,y-1});
        } else {
          q.push_front({x,y-1});
        }
      } 
    }
    if(is(x,y+1)) {
      if(dist[x][y+1] > dist[x][y]+(a[x][y] != a[x][y+1])) {
        dist[x][y+1] = dist[x][y]+(a[x][y] != a[x][y+1]);
        if(a[x][y] != a[x][y+1]) {
          q.push_back({x,y+1});
        } else {
          q.push_front({x,y+1});
        }
      } 
    }
  }
  std::cout<<ans<<"\n";
}


signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    //frx("perimeter");
    #ifdef LOCAL  
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    auto start = std::chrono::high_resolution_clock::now();
    #endif
    int t = 1;
    //std::cin >> t;
    while (t--) {
        solve();
    }
    #ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << elapsed.count() << " seconds\n";
    #endif
    return 0;  
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1796 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 4 ms 2268 KB Output is correct
13 Correct 2 ms 2140 KB Output is correct
14 Correct 3 ms 2304 KB Output is correct
15 Correct 9 ms 4664 KB Output is correct
16 Correct 10 ms 4444 KB Output is correct
17 Correct 8 ms 4280 KB Output is correct
18 Correct 6 ms 3980 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15680 KB Output is correct
2 Correct 41 ms 19036 KB Output is correct
3 Correct 301 ms 157088 KB Output is correct
4 Correct 77 ms 40788 KB Output is correct
5 Correct 201 ms 91216 KB Output is correct
6 Correct 693 ms 183240 KB Output is correct
7 Correct 8 ms 16312 KB Output is correct
8 Correct 6 ms 15708 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 7 ms 16220 KB Output is correct
12 Correct 1 ms 1244 KB Output is correct
13 Correct 41 ms 19100 KB Output is correct
14 Correct 30 ms 11892 KB Output is correct
15 Correct 20 ms 12892 KB Output is correct
16 Correct 17 ms 7516 KB Output is correct
17 Correct 110 ms 43856 KB Output is correct
18 Correct 74 ms 43344 KB Output is correct
19 Correct 73 ms 40640 KB Output is correct
20 Correct 59 ms 37456 KB Output is correct
21 Correct 155 ms 94552 KB Output is correct
22 Correct 179 ms 91216 KB Output is correct
23 Correct 192 ms 78404 KB Output is correct
24 Correct 185 ms 92568 KB Output is correct
25 Correct 285 ms 156852 KB Output is correct
26 Correct 402 ms 222212 KB Output is correct
27 Correct 520 ms 191808 KB Output is correct
28 Correct 677 ms 183372 KB Output is correct
29 Correct 662 ms 184040 KB Output is correct
30 Correct 603 ms 182984 KB Output is correct
31 Correct 426 ms 103884 KB Output is correct
32 Correct 520 ms 187912 KB Output is correct