oj.uz

Submission #1094830

# Submission time Handle Problem Language Result Execution time Memory
1094830 2024-09-30T16:05:06 Z wrtt Tracks in the Snow (BOI13_tracks) C++14
9.89583 / 100
 2000 ms 1048576 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 << "]";
}
*/


void solve() {
  int h,w;
  cin >> h >> w;
  int a[h][w];
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      char c;
      cin >> c;
      if(c=='F') {
        a[i][j] = 1;
      }
      else if(c=='R') {
        a[i][j] = 0;
      }
      else {
        a[i][j] = 2;
      }
    }
  }
  vector<pair<int,int>> g[h*w+1];
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      if(a[i][j] != 2) {
        if(i+1 < h && a[i+1][j] != 2) {
          g[i*w+j].pb((i+1)*w+j, a[i][j] != a[i+1][j]);
          g[(i+1)*w+j+1].pb(i*w+j, a[i][j] != a[i+1][j]);
        }
        if(j+1 < w && a[i][j+1] != 2) {
          g[i*w+j].pb(i*w+j+1, a[i][j] != a[i][j+1]);
          g[i*w+j+1].pb(i*w+j, a[i][j] != a[i][j+1]);
        }
        if(i-1 >= 0 && a[i-1][j] != 2) {
          g[i*w+j].pb((i-1)*w+j, a[i][j] != a[i-1][j]);
          g[(i-1)*w+j+1].pb(i*w+j, a[i][j] != a[i-1][j]);
        }
        if(j-1 >= 0 && a[i][j-1] != 2) {
          g[i*w+j].pb(i*w+j-1, a[i][j] != a[i][j-1]);
          g[i*w+j-1].pb(i*w+j, a[i][j] != a[i][j-1]);
        }
      }
    }
  }
  // 0-1 BFS
  int dist[h*w+1];
  for(int i = 0; i < h*w+1; ++i) {
    dist[i] = 1e18;
  }
  dist[0] = 0;
  deque<int> q;
  q.push_back(0);
  while(!q.empty()) {
    int c = q.front();
    q.pop_front();
    for(auto u : g[c]) {
      int v = u.first;
      int w = u.second;
      if(dist[v] > dist[c]+w) {
        dist[v] = dist[c]+w;
        if(w) {
          q.push_front(v);
        }
        else {
          q.push_back(v);
        }
      }
    }
  }
  int ans = 0;
  for(int i = 0; i < h*w+1; ++i) {
    if(dist[i] != 1e18) {
      ans=mx(ans, dist[i]);
    }
  }
  cout<<ans+1<<"\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
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1410 ms 143428 KB Output isn't correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 716 KB Output isn't correct
4 Incorrect 42 ms 28240 KB Output isn't correct
5 Incorrect 57 ms 5980 KB Output isn't correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Incorrect 2 ms 1116 KB Output isn't correct
9 Incorrect 1 ms 860 KB Output isn't correct
10 Incorrect 33 ms 6236 KB Output isn't correct
11 Incorrect 10 ms 7512 KB Output isn't correct
12 Incorrect 266 ms 35040 KB Output isn't correct
13 Incorrect 58 ms 5980 KB Output isn't correct
14 Incorrect 58 ms 6128 KB Output isn't correct
15 Incorrect 528 ms 38480 KB Output isn't correct
16 Incorrect 1457 ms 143168 KB Output isn't correct
17 Incorrect 400 ms 23496 KB Output isn't correct
18 Incorrect 42 ms 28100 KB Output isn't correct

Subtask #2
6.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3672 KB Output isn't correct
2 Execution timed out 2096 ms 146416 KB Time limit exceeded
3 Runtime error 1071 ms 1048576 KB Execution killed with signal 9
4 Execution timed out 2057 ms 213692 KB Time limit exceeded
5 Execution timed out 2081 ms 713752 KB Time limit exceeded
6 Runtime error 959 ms 1048576 KB Execution killed with signal 9
7 Incorrect 4 ms 3416 KB Output isn't correct
8 Incorrect 4 ms 3672 KB Output isn't correct
9 Incorrect 212 ms 6572 KB Output isn't correct
10 Correct 2 ms 2396 KB Output is correct
11 Incorrect 3 ms 2948 KB Output isn't correct
12 Incorrect 3 ms 2396 KB Output isn't correct
13 Execution timed out 2105 ms 146292 KB Time limit exceeded
14 Incorrect 1459 ms 85908 KB Output isn't correct
15 Correct 94 ms 67252 KB Output is correct
16 Incorrect 1547 ms 75904 KB Output isn't correct
17 Execution timed out 2087 ms 371296 KB Time limit exceeded
18 Correct 403 ms 264944 KB Output is correct
19 Execution timed out 2065 ms 213840 KB Time limit exceeded
20 Execution timed out 2041 ms 240972 KB Time limit exceeded
21 Execution timed out 2045 ms 632656 KB Time limit exceeded
22 Execution timed out 2040 ms 713812 KB Time limit exceeded
23 Execution timed out 2079 ms 724052 KB Time limit exceeded
24 Incorrect 624 ms 600152 KB Output isn't correct
25 Runtime error 1083 ms 1048576 KB Execution killed with signal 9
26 Runtime error 1083 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1027 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1078 ms 1048576 KB Execution killed with signal 9
29 Runtime error 977 ms 1048576 KB Execution killed with signal 9
30 Runtime error 931 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1206 ms 1048576 KB Execution killed with signal 9
32 Runtime error 948 ms 1048576 KB Execution killed with signal 9