oj.uz

Submission #605131

# Submission time Handle Problem Language Result Execution time Memory
605131 2022-07-25T13:18:22 Z jackkkk Tracks in the Snow (BOI13_tracks) C++11
19.7917 / 100
 1666 ms 1048576 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];
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]='.';
    }
  }
  for(int i = 1; i <= n; i++){
    string s; cin >> s;
    for(int j = 1; j <= m; j++){
      grid[i][j]=s[j-1];
    }
  }
  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(id[i][j] != id[i][j+1]){
        adj[id[i][j]].insert(id[i][j+1]);
        adj[id[i][j+1]].insert(id[i][j]);
      }
      if(id[i][j] != id[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();
}

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 28720 KB Output isn't correct
2 Incorrect 8 ms 16084 KB Output isn't correct
3 Incorrect 10 ms 16304 KB Output isn't correct
4 Correct 15 ms 19484 KB Output is correct
5 Incorrect 16 ms 19892 KB Output isn't correct
6 Incorrect 10 ms 16084 KB Output isn't correct
7 Incorrect 8 ms 16264 KB Output isn't correct
8 Correct 10 ms 16212 KB Output is correct
9 Incorrect 10 ms 16604 KB Output isn't correct
10 Incorrect 15 ms 19648 KB Output isn't correct
11 Correct 9 ms 17112 KB Output is correct
12 Incorrect 20 ms 21196 KB Output isn't correct
13 Incorrect 16 ms 19912 KB Output isn't correct
14 Incorrect 18 ms 19920 KB Output isn't correct
15 Incorrect 41 ms 29868 KB Output isn't correct
16 Incorrect 46 ms 28756 KB Output isn't correct
17 Incorrect 45 ms 30016 KB Output isn't correct
18 Correct 18 ms 19484 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 33076 KB Output isn't correct
2 Incorrect 175 ms 87904 KB Output isn't correct
3 Incorrect 948 ms 520176 KB Output isn't correct
4 Incorrect 252 ms 119968 KB Output isn't correct
5 Runtime error 1137 ms 1048576 KB Execution killed with signal 9
6 Correct 995 ms 226964 KB Output is correct
7 Incorrect 24 ms 33524 KB Output isn't correct
8 Incorrect 21 ms 33024 KB Output isn't correct
9 Incorrect 13 ms 18176 KB Output isn't correct
10 Incorrect 10 ms 16852 KB Output isn't correct
11 Incorrect 17 ms 32568 KB Output isn't correct
12 Incorrect 15 ms 20052 KB Output isn't correct
13 Incorrect 175 ms 87860 KB Output isn't correct
14 Incorrect 102 ms 58512 KB Output isn't correct
15 Incorrect 117 ms 68556 KB Output isn't correct
16 Incorrect 71 ms 47296 KB Output isn't correct
17 Incorrect 397 ms 197336 KB Output isn't correct
18 Incorrect 430 ms 213024 KB Output isn't correct
19 Incorrect 226 ms 119924 KB Output isn't correct
20 Incorrect 230 ms 135980 KB Output isn't correct
21 Incorrect 523 ms 328024 KB Output isn't correct
22 Runtime error 1037 ms 1048576 KB Execution killed with signal 9
23 Incorrect 657 ms 359428 KB Output isn't correct
24 Incorrect 803 ms 521724 KB Output isn't correct
25 Incorrect 1666 ms 795156 KB Output isn't correct
26 Correct 373 ms 82944 KB Output is correct
27 Correct 451 ms 98384 KB Output is correct
28 Correct 940 ms 226904 KB Output is correct
29 Correct 753 ms 173676 KB Output is correct
30 Correct 707 ms 148976 KB Output is correct
31 Incorrect 1666 ms 459128 KB Output isn't correct
32 Incorrect 582 ms 133616 KB Output isn't correct