oj.uz

Submission #604192

# Submission time Handle Problem Language Result Execution time Memory
604192 2022-07-24T20:32:17 Z jackkkk Tracks in the Snow (BOI13_tracks) C++11
71.5625 / 100
 1181 ms 1048576 KB 
// EMPTY
// 

#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>
using namespace std;


void quit() {
  cout.flush();
  exit(0);
}
char grid[4002][4002];
vector<unordered_set<int>> adj;
int id[4001][4001];
int curr_id = 1;
deque <pair<int, int>> dq;
vector<pair<int, int>> gto = {{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.clear();
  dq.emplace_back(a, b);
  while(!dq.empty()){
    auto curr = dq.front();
    dq.pop_front();
    for(auto to : gto){
      pair<int, int> nxt = {curr.first+to.first, curr.second+to.second};
      if(grid[nxt.first][nxt.second] == c){
        id[nxt.first][nxt.second]=curr_id;
        grid[nxt.first][nxt.second] = '.';
        dq.push_back(nxt);
      }
      if(id[nxt.first][nxt.second]!=0 && id[nxt.first][nxt.second] != curr_id){
        adj[id[nxt.first][nxt.second]].insert(curr_id);
        adj[curr_id].insert(id[nxt.first][nxt.second]);
      }
    }
  }
  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);
  adj.resize(4000*4000+1);
  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);
      }
    }
  }
  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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 903292 KB Output is correct
2 Correct 515 ms 892792 KB Output is correct
3 Correct 497 ms 893064 KB Output is correct
4 Correct 486 ms 895880 KB Output is correct
5 Correct 513 ms 895588 KB Output is correct
6 Correct 497 ms 892728 KB Output is correct
7 Correct 484 ms 892948 KB Output is correct
8 Correct 493 ms 892912 KB Output is correct
9 Correct 480 ms 893136 KB Output is correct
10 Correct 477 ms 895380 KB Output is correct
11 Correct 503 ms 893876 KB Output is correct
12 Correct 506 ms 897048 KB Output is correct
13 Correct 522 ms 895612 KB Output is correct
14 Correct 492 ms 895652 KB Output is correct
15 Correct 519 ms 902948 KB Output is correct
16 Correct 509 ms 903280 KB Output is correct
17 Correct 516 ms 902492 KB Output is correct
18 Correct 501 ms 895984 KB Output is correct

Subtask #2
41.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 909132 KB Output is correct
2 Correct 631 ms 938476 KB Output is correct
3 Runtime error 946 ms 1048576 KB Execution killed with signal 11
4 Correct 677 ms 960844 KB Output is correct
5 Runtime error 600 ms 1048576 KB Execution killed with signal 9
6 Runtime error 1043 ms 1048576 KB Execution killed with signal 11
7 Correct 517 ms 909644 KB Output is correct
8 Correct 497 ms 909172 KB Output is correct
9 Correct 493 ms 894192 KB Output is correct
10 Correct 532 ms 893196 KB Output is correct
11 Correct 505 ms 908952 KB Output is correct
12 Correct 501 ms 895332 KB Output is correct
13 Correct 642 ms 938880 KB Output is correct
14 Correct 587 ms 920836 KB Output is correct
15 Correct 577 ms 926612 KB Output is correct
16 Correct 557 ms 913748 KB Output is correct
17 Correct 842 ms 1006248 KB Output is correct
18 Correct 874 ms 1014324 KB Output is correct
19 Correct 677 ms 961140 KB Output is correct
20 Correct 673 ms 968556 KB Output is correct
21 Runtime error 687 ms 1048576 KB Execution killed with signal 9
22 Runtime error 665 ms 1048576 KB Execution killed with signal 9
23 Runtime error 683 ms 1048576 KB Execution killed with signal 9
24 Runtime error 646 ms 1048576 KB Execution killed with signal 9
25 Runtime error 964 ms 1048576 KB Execution killed with signal 11
26 Correct 848 ms 948344 KB Output is correct
27 Runtime error 1058 ms 1048576 KB Execution killed with signal 11
28 Runtime error 1036 ms 1048576 KB Execution killed with signal 11
29 Runtime error 1049 ms 1048576 KB Execution killed with signal 11
30 Correct 1181 ms 998464 KB Output is correct
31 Runtime error 869 ms 1048576 KB Execution killed with signal 9
32 Runtime error 950 ms 1048576 KB Execution killed with signal 11