oj.uz

Submission #917772

# Submission time Handle Problem Language Result Execution time Memory
917772 2024-01-28T18:52:20 Z Winter Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 949 ms 245872 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;
  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 11 ms 3160 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 5 ms 2364 KB Output isn't correct
5 Incorrect 3 ms 1332 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 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 604 KB Output isn't correct
10 Incorrect 3 ms 1372 KB Output isn't correct
11 Incorrect 2 ms 860 KB Output isn't correct
12 Incorrect 4 ms 1232 KB Output isn't correct
13 Incorrect 3 ms 1372 KB Output isn't correct
14 Incorrect 4 ms 1240 KB Output isn't correct
15 Incorrect 9 ms 3676 KB Output isn't correct
16 Incorrect 9 ms 2908 KB Output isn't correct
17 Incorrect 8 ms 2916 KB Output isn't correct
18 Incorrect 5 ms 2396 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1884 KB Output isn't correct
2 Incorrect 49 ms 23324 KB Output isn't correct
3 Incorrect 493 ms 245872 KB Output isn't correct
4 Incorrect 118 ms 39000 KB Output isn't correct
5 Incorrect 271 ms 164636 KB Output isn't correct
6 Incorrect 578 ms 187028 KB Output isn't correct
7 Incorrect 3 ms 1628 KB Output isn't correct
8 Incorrect 3 ms 1528 KB Output isn't correct
9 Incorrect 2 ms 1116 KB Output isn't correct
10 Incorrect 2 ms 972 KB Output isn't correct
11 Incorrect 3 ms 1748 KB Output isn't correct
12 Incorrect 1 ms 856 KB Output isn't correct
13 Incorrect 55 ms 23340 KB Output isn't correct
14 Incorrect 26 ms 13660 KB Output isn't correct
15 Incorrect 34 ms 15196 KB Output isn't correct
16 Incorrect 20 ms 9704 KB Output isn't correct
17 Incorrect 122 ms 60224 KB Output isn't correct
18 Incorrect 219 ms 58888 KB Output isn't correct
19 Incorrect 115 ms 38992 KB Output isn't correct
20 Incorrect 116 ms 53172 KB Output isn't correct
21 Incorrect 297 ms 147616 KB Output isn't correct
22 Incorrect 259 ms 164180 KB Output isn't correct
23 Incorrect 238 ms 114960 KB Output isn't correct
24 Incorrect 262 ms 141000 KB Output isn't correct
25 Incorrect 949 ms 234896 KB Output isn't correct
26 Incorrect 390 ms 222732 KB Output isn't correct
27 Incorrect 475 ms 212776 KB Output isn't correct
28 Incorrect 589 ms 186836 KB Output isn't correct
29 Incorrect 575 ms 183528 KB Output isn't correct
30 Incorrect 521 ms 191960 KB Output isn't correct
31 Incorrect 397 ms 103536 KB Output isn't correct
32 Incorrect 490 ms 190544 KB Output isn't correct