oj.uz

Submission #605159

# Submission time Handle Problem Language Result Execution time Memory
605159 2022-07-25T13:33:08 Z jackkkk Tracks in the Snow (BOI13_tracks) C++11
0 / 100
 18 ms 32300 KB 
// Tracks in the Snow
// https://oj.uz/problem/view/BOI13_tracks

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <cassert>
using namespace std;


void quit() {
  cout.flush();
  exit(0);
}
char grid[4002][4002]; char gridcpy[4002][4002];
vector<unordered_set<int>> adj;
int id[4002][4002];
int curr_id = 1;
deque <pair<int, int>> dq;
pair<int, int> gto[4] = {{1,0},{0,1},{-1,0},{0,-1}};
void flood(int a, int b){
  id[a][b]=curr_id;
  char c = grid[a][b];
  grid[a][b]='.';
  dq.emplace_back(a, b);
  while(!dq.empty()){
    auto curr = dq.front();
    dq.pop_front();
    for(auto to : gto){
      int nxt1 = curr.first+to.first, nxt2 = curr.second+to.second;
      if(grid[nxt1][nxt2] == c){
        id[nxt1][nxt2]=curr_id;
        grid[nxt1][nxt2] = '.';
        dq.emplace_back(nxt1, nxt2);
      }
    }
  }
  curr_id++;
}

int main(void){
  freopen("qwer.in", "r", stdin);
  freopen("qwer.out", "w", stdout);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m; cin >> n >> m;
  for(int i = 0; i < 4002; i++){
    for(int j = 0; j < 4002; j++){
      grid[i][j]='.';
      gridcpy[i][j]='.';
    }
  }
  for(int i = 1; i <= n; i++){
    string s; cin >> s;
    for(int j = 1; j <= m; j++){
      grid[i][j]=s[j-1];
      gridcpy[i][j]=grid[i][j];
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(grid[i][j] != '.'){
        flood(i, j);
      }
    }
  }
  adj.resize(curr_id+10);
  for(int i = 1; i < n; i++){
    for(int j = 1; j < m; j++){
      if(gridcpy[i][j]!= '.' && gridcpy[i][j+1] != '.' && gridcpy[i][j] != gridcpy[i][j+1]){
        adj[id[i][j]].insert(id[i][j+1]);
        adj[id[i][j+1]].insert(id[i][j]);
      }
      if(gridcpy[i][j]!= '.' && gridcpy[i+1][j] != '.' && gridcpy[i][j] != gridcpy[i+1][j]){
        adj[id[i][j]].insert(id[i+1][j]);
        adj[id[i+1][j]].insert(id[i][j]);
      }
    }
  }
  deque <int> dq;
  dq.push_back(1);
  vector <int> dist(curr_id, 1e9);
  dist[1]=0;
  while(!dq.empty()){
    int curr = dq.front();
    dq.pop_front();
    for(int nxt : adj[curr]){
      if(dist[curr]+1 < dist[nxt]){
        dist[nxt]=dist[curr]+1;
        dq.push_back(nxt);
      }
    }
  }

  int ans = 0;
  for(int i = 1; i < curr_id; i++){
    ans = max(ans, dist[i]);
  }
  cout << ans+1 << "\n";
  quit();
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   freopen("qwer.in", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   freopen("qwer.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 32212 KB Output isn't correct
2 Incorrect 13 ms 32212 KB Output isn't correct
3 Incorrect 14 ms 32196 KB Output isn't correct
4 Incorrect 13 ms 32212 KB Output isn't correct
5 Incorrect 13 ms 32212 KB Output isn't correct
6 Incorrect 14 ms 32288 KB Output isn't correct
7 Incorrect 14 ms 32300 KB Output isn't correct
8 Incorrect 16 ms 32256 KB Output isn't correct
9 Incorrect 14 ms 32172 KB Output isn't correct
10 Incorrect 14 ms 32276 KB Output isn't correct
11 Incorrect 15 ms 32212 KB Output isn't correct
12 Incorrect 17 ms 32248 KB Output isn't correct
13 Incorrect 15 ms 32212 KB Output isn't correct
14 Incorrect 15 ms 32212 KB Output isn't correct
15 Incorrect 14 ms 32268 KB Output isn't correct
16 Incorrect 14 ms 32296 KB Output isn't correct
17 Incorrect 15 ms 32228 KB Output isn't correct
18 Incorrect 14 ms 32212 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 32292 KB Output isn't correct
2 Incorrect 16 ms 32224 KB Output isn't correct
3 Incorrect 17 ms 32288 KB Output isn't correct
4 Incorrect 16 ms 32196 KB Output isn't correct
5 Incorrect 15 ms 32252 KB Output isn't correct
6 Incorrect 14 ms 32212 KB Output isn't correct
7 Incorrect 15 ms 32212 KB Output isn't correct
8 Incorrect 14 ms 32212 KB Output isn't correct
9 Incorrect 14 ms 32192 KB Output isn't correct
10 Incorrect 15 ms 32184 KB Output isn't correct
11 Incorrect 14 ms 32212 KB Output isn't correct
12 Incorrect 15 ms 32288 KB Output isn't correct
13 Incorrect 14 ms 32212 KB Output isn't correct
14 Incorrect 17 ms 32232 KB Output isn't correct
15 Incorrect 14 ms 32212 KB Output isn't correct
16 Incorrect 14 ms 32212 KB Output isn't correct
17 Incorrect 14 ms 32260 KB Output isn't correct
18 Incorrect 16 ms 32212 KB Output isn't correct
19 Incorrect 15 ms 32272 KB Output isn't correct
20 Incorrect 18 ms 32248 KB Output isn't correct
21 Incorrect 17 ms 32196 KB Output isn't correct
22 Incorrect 18 ms 32212 KB Output isn't correct
23 Incorrect 14 ms 32276 KB Output isn't correct
24 Incorrect 14 ms 32212 KB Output isn't correct
25 Incorrect 14 ms 32188 KB Output isn't correct
26 Incorrect 15 ms 32212 KB Output isn't correct
27 Incorrect 15 ms 32212 KB Output isn't correct
28 Incorrect 14 ms 32208 KB Output isn't correct
29 Incorrect 15 ms 32260 KB Output isn't correct
30 Incorrect 15 ms 32296 KB Output isn't correct
31 Incorrect 14 ms 32268 KB Output isn't correct
32 Incorrect 15 ms 32212 KB Output isn't correct