oj.uz

Submission #917776

# Submission time Handle Problem Language Result Execution time Memory
917776 2024-01-28T18:59:03 Z Winter Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 622 ms 211164 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, '.'));
  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]=1; 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]!='.'){
      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]!='.'){
      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]!='.'){
      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]!='.'){
      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.
Can't count dots for some reason.
*/

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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2648 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 5 ms 2136 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 2 ms 1116 KB Output is correct
15 Correct 8 ms 2828 KB Output is correct
16 Correct 9 ms 2820 KB Output is correct
17 Correct 8 ms 2656 KB Output is correct
18 Correct 5 ms 2140 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB Output is correct
2 Correct 40 ms 14620 KB Output is correct
3 Correct 297 ms 143952 KB Output is correct
4 Correct 95 ms 34236 KB Output is correct
5 Correct 174 ms 81296 KB Output is correct
6 Correct 622 ms 171244 KB Output is correct
7 Correct 2 ms 1368 KB Output is correct
8 Correct 2 ms 1368 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 760 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 40 ms 14424 KB Output is correct
14 Correct 24 ms 8536 KB Output is correct
15 Correct 24 ms 9304 KB Output is correct
16 Correct 18 ms 6232 KB Output is correct
17 Correct 107 ms 36972 KB Output is correct
18 Correct 84 ms 36444 KB Output is correct
19 Correct 88 ms 34136 KB Output is correct
20 Correct 73 ms 31320 KB Output is correct
21 Correct 179 ms 84060 KB Output is correct
22 Correct 188 ms 81232 KB Output is correct
23 Correct 208 ms 69968 KB Output is correct
24 Correct 199 ms 82004 KB Output is correct
25 Correct 587 ms 143956 KB Output is correct
26 Correct 378 ms 211164 KB Output is correct
27 Correct 514 ms 196932 KB Output is correct
28 Correct 569 ms 171244 KB Output is correct
29 Correct 561 ms 167844 KB Output is correct
30 Correct 521 ms 176680 KB Output is correct
31 Correct 383 ms 93264 KB Output is correct
32 Correct 446 ms 174424 KB Output is correct