oj.uz

Submission #917774

# Submission time Handle Problem Language Result Execution time Memory
917774 2024-01-28T18:53:51 Z Winter Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 893 ms 231004 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx,avx2,popcnt")
#pragma GCC optimize("O3")
#define int long long
#define pb push_back
#define pii pair<int, int>
const int MA = 1e5+5;
const int MX = 2e9;
const int MD = 998244353;
#define watch(x) cout << #x << "=" << x << endl
void setIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
int32_t main(){
  //setIO("nocross"); 
  ios_base::sync_with_stdio(NULL); cin.tie(NULL);
  int n, m; cin >> n >> m;
  vector<vector<char>> v(n+2, vector<char>(m+2, 'x'));
  vector<vector<int>> dist(n+2, vector<int>(m+2, MX));
  vector<vector<bool>> vis(n+2, vector<bool>(m+2, false));
  for(int i = 1; i<=n; i++){
    for(int j = 1; j<=m; j++){
      cin >> v[i][j];
    }
  }
  deque<pii> q; q.push_front({1, 1}); 
  dist[1][1]=0; vis[1][1]=true;
  while(!q.empty()){
    int a, b; tie(a, b)=q.front(); q.pop_front();
    if(vis[a+1][b]==false&&v[a+1][b]!='x'){
      int x=0;
      if(v[a][b]!=v[a+1][b]) x=1;
      dist[a+1][b]=min(dist[a+1][b], dist[a][b]+x);
      if(x==0) q.push_front({a+1, b});
      else q.push_back({a+1, b}); 
      vis[a+1][b]=true;
    }
    if(vis[a-1][b]==false&&v[a-1][b]!='x'){
      int x=0;
      if(v[a][b]!=v[a-1][b]) x=1;
      dist[a-1][b]=min(dist[a-1][b], dist[a][b]+x);
      if(x==0) q.push_front({a-1, b});
      else q.push_back({a-1, b}); 
      vis[a-1][b]=true;
    }
    if(vis[a][b+1]==false&&v[a][b+1]!='x'){
      int x=0;
      if(v[a][b]!=v[a][b+1]) x=1;
      dist[a][b+1]=min(dist[a][b+1], dist[a][b]+x);
      if(x==0) q.push_front({a, b+1});
      else q.push_back({a, b+1});
      vis[a][b+1]=true;
    }
    if(vis[a][b-1]==false&&v[a][b-1]!='x'){
      int x=0;
      if(v[a][b]!=v[a][b-1]) x=1;
      dist[a][b-1]=min(dist[a][b-1], dist[a][b]+x);
      if(x==0) q.push_front({a, b-1});
      else q.push_back({a, b-1});
      vis[a][b-1]=true;
    }
  }
  int ans=0;
  for(int i = 1; i<=n; i++){
    for(int j = 1; j<=m; j++){
      if(dist[i][j]!=MX) ans=max(ans, dist[i][j]);
    }
  }
  cout << ans << endl;
  return 0;
}
/*
Amount of animals is the amount of fox and rabbit paths counted separately.
Somehow the answer is related to the amount of components.
int ans=1;
Number of F components completely surrounded by R, or other way around.
The logic is that then there must be one more animal because it is not
possible that F didn't move out and cross over the R.
But there is one counter-case to that logic.
The depth of the most recursive pocket?
Like a circle round' a circle round' a circle and so on..
Distance can be as going from one type of element to another type of element.
Find shortest paths to every place and in that answer array, what
is the biggest distance stored.
Need 0/1 BFS.
*/

Compilation message

tracks.cpp: In function 'void setIO(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((s + ".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((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2652 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 5 ms 2140 KB Output isn't correct
5 Incorrect 3 ms 1372 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 2 ms 1372 KB Output isn't correct
11 Incorrect 2 ms 860 KB Output isn't correct
12 Incorrect 4 ms 1116 KB Output isn't correct
13 Incorrect 3 ms 1372 KB Output isn't correct
14 Incorrect 3 ms 1372 KB Output isn't correct
15 Incorrect 11 ms 3420 KB Output isn't correct
16 Incorrect 9 ms 2648 KB Output isn't correct
17 Incorrect 8 ms 2904 KB Output isn't correct
18 Incorrect 5 ms 2140 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1628 KB Output isn't correct
2 Incorrect 55 ms 21716 KB Output isn't correct
3 Incorrect 532 ms 231004 KB Output isn't correct
4 Incorrect 114 ms 35424 KB Output isn't correct
5 Incorrect 263 ms 155552 KB Output isn't correct
6 Incorrect 577 ms 171300 KB Output isn't correct
7 Incorrect 2 ms 1628 KB Output isn't correct
8 Incorrect 2 ms 1628 KB Output isn't correct
9 Incorrect 2 ms 1116 KB Output isn't correct
10 Incorrect 1 ms 1116 KB Output isn't correct
11 Incorrect 3 ms 1628 KB Output isn't correct
12 Incorrect 1 ms 860 KB Output isn't correct
13 Incorrect 46 ms 21868 KB Output isn't correct
14 Incorrect 26 ms 12884 KB Output isn't correct
15 Incorrect 33 ms 14164 KB Output isn't correct
16 Incorrect 19 ms 9048 KB Output isn't correct
17 Incorrect 123 ms 56268 KB Output isn't correct
18 Incorrect 221 ms 54536 KB Output isn't correct
19 Incorrect 115 ms 35464 KB Output isn't correct
20 Incorrect 105 ms 49840 KB Output isn't correct
21 Incorrect 289 ms 138928 KB Output isn't correct
22 Incorrect 260 ms 155380 KB Output isn't correct
23 Incorrect 237 ms 107176 KB Output isn't correct
24 Incorrect 249 ms 132020 KB Output isn't correct
25 Incorrect 893 ms 219384 KB Output isn't correct
26 Incorrect 371 ms 211464 KB Output isn't correct
27 Incorrect 469 ms 196944 KB Output isn't correct
28 Incorrect 579 ms 171236 KB Output isn't correct
29 Incorrect 578 ms 167840 KB Output isn't correct
30 Incorrect 521 ms 176644 KB Output isn't correct
31 Incorrect 398 ms 93336 KB Output isn't correct
32 Incorrect 493 ms 174900 KB Output isn't correct