oj.uz

Submission #1094307

# Submission time Handle Problem Language Result Execution time Memory
1094307 2024-09-29T10:26:06 Z MattNattFeczan Tracks in the Snow (BOI13_tracks) C++14
73.75 / 100
 997 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 4000;
string S[N];
vector<pair<int,int>>Graf1[N*N]; //czy rozne kolory, wierzcholek
int idx[N*N], color[N*N], c=1;
vector<int>Graf[N*N];

void DFS1(int n, int v){
  color[n] = c, idx[n] = v;
  for(auto& elm : Graf1[n]){
    if(!color[elm.second] && elm.first == 0){
      DFS1(elm.second, v);
    }
  }
}

int makeTree(int n, int m){
  int v = 0, d = 0;
  for(int i=0;i<n*m;i++){
    if(!color[i])
      DFS1(i, v++);
  }
  c++;
  for(int i=0;i<n*m;i++){
    for(auto& elm : Graf1[i]){
      if(idx[elm.second] != idx[i])
        Graf[idx[i]].push_back(idx[elm.second]);
    }
    Graf1[i].clear();
  }
  queue<pair<int,int>>Q;
  Q.push({0, 1});
  while(!Q.empty()){
    auto now = Q.front();
    Q.pop();
    if(color[now.first] == c)
      continue;
    color[now.first] = c, d = max(d, now.second);
    for(auto& elm : Graf[now.first]){
      if(color[elm] != c){
        Q.push({elm, now.second+1});
      }
    }
  }
  return d;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>S[i];
    for(int j=0;j<m;j++){
      if(S[i][j] == '.')
        continue;
      if(i != 0){
        if(S[i-1][j] == S[i][j]){
          Graf1[i*m+j].push_back({0, (i-1)*m+j}), Graf1[(i-1)*m+j].push_back({0, i*m+j});
        }
        else if(S[i-1][j] != '.'){
          Graf1[i*m+j].push_back({1, (i-1)*m+j}), Graf1[(i-1)*m+j].push_back({1, i*m+j});
        }
      }
      if(j != 0){
        if(S[i][j-1] == S[i][j]){
          Graf1[i*m+j-1].push_back({0, i*m+j}), Graf1[i*m+j].push_back({0, i*m+j-1});
        }
        else if(S[i][j-1] != '.'){
          Graf1[i*m+j-1].push_back({1, i*m+j}), Graf1[i*m+j].push_back({1, i*m+j-1});
        }
      }
    }
  }
  cout<<makeTree(n, m)<<"\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 768120 KB Output is correct
2 Correct 326 ms 751956 KB Output is correct
3 Correct 320 ms 752016 KB Output is correct
4 Correct 338 ms 762408 KB Output is correct
5 Correct 292 ms 753748 KB Output is correct
6 Correct 287 ms 751956 KB Output is correct
7 Correct 280 ms 751952 KB Output is correct
8 Correct 278 ms 752212 KB Output is correct
9 Correct 274 ms 752212 KB Output is correct
10 Correct 281 ms 754084 KB Output is correct
11 Correct 273 ms 754772 KB Output is correct
12 Correct 317 ms 757580 KB Output is correct
13 Correct 303 ms 753628 KB Output is correct
14 Correct 311 ms 753748 KB Output is correct
15 Correct 335 ms 764780 KB Output is correct
16 Correct 344 ms 768480 KB Output is correct
17 Correct 332 ms 759888 KB Output is correct
18 Correct 322 ms 762448 KB Output is correct

Subtask #2
43.75 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 752980 KB Output is correct
2 Correct 453 ms 802900 KB Output is correct
3 Runtime error 722 ms 1048576 KB Execution killed with signal 9
4 Correct 504 ms 814340 KB Output is correct
5 Runtime error 691 ms 1048576 KB Execution killed with signal 9
6 Runtime error 789 ms 1048576 KB Execution killed with signal 9
7 Correct 301 ms 752904 KB Output is correct
8 Correct 318 ms 753232 KB Output is correct
9 Correct 296 ms 754196 KB Output is correct
10 Correct 300 ms 752652 KB Output is correct
11 Correct 336 ms 752724 KB Output is correct
12 Correct 314 ms 753192 KB Output is correct
13 Correct 444 ms 802900 KB Output is correct
14 Correct 400 ms 781748 KB Output is correct
15 Correct 393 ms 774404 KB Output is correct
16 Correct 388 ms 777980 KB Output is correct
17 Correct 641 ms 881732 KB Output is correct
18 Correct 681 ms 839512 KB Output is correct
19 Correct 539 ms 814160 KB Output is correct
20 Correct 480 ms 831060 KB Output is correct
21 Correct 765 ms 958412 KB Output is correct
22 Runtime error 670 ms 1048576 KB Execution killed with signal 9
23 Correct 943 ms 1005648 KB Output is correct
24 Correct 693 ms 973908 KB Output is correct
25 Runtime error 997 ms 1048576 KB Execution killed with signal 9
26 Runtime error 746 ms 1048576 KB Execution killed with signal 9
27 Runtime error 723 ms 1048576 KB Execution killed with signal 9
28 Runtime error 741 ms 1048576 KB Execution killed with signal 9
29 Runtime error 730 ms 1048576 KB Execution killed with signal 9
30 Runtime error 754 ms 1048576 KB Execution killed with signal 9
31 Runtime error 824 ms 1048576 KB Execution killed with signal 9
32 Runtime error 754 ms 1048576 KB Execution killed with signal 9