oj.uz

Submission #1094308

# Submission time Handle Problem Language Result Execution time Memory
1094308 2024-09-29T10:27:53 Z MattNattFeczan Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 399 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;
set<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]].insert(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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 351 ms 1048576 KB Execution killed with signal 9
2 Runtime error 367 ms 1048576 KB Execution killed with signal 9
3 Runtime error 367 ms 1048576 KB Execution killed with signal 9
4 Runtime error 371 ms 1048576 KB Execution killed with signal 9
5 Runtime error 369 ms 1048576 KB Execution killed with signal 9
6 Runtime error 364 ms 1048576 KB Execution killed with signal 9
7 Runtime error 383 ms 1048576 KB Execution killed with signal 9
8 Runtime error 357 ms 1048576 KB Execution killed with signal 9
9 Runtime error 363 ms 1048576 KB Execution killed with signal 9
10 Runtime error 360 ms 1048576 KB Execution killed with signal 9
11 Runtime error 389 ms 1048576 KB Execution killed with signal 9
12 Runtime error 354 ms 1048576 KB Execution killed with signal 9
13 Runtime error 375 ms 1048576 KB Execution killed with signal 9
14 Runtime error 362 ms 1048576 KB Execution killed with signal 9
15 Runtime error 388 ms 1048576 KB Execution killed with signal 9
16 Runtime error 386 ms 1048576 KB Execution killed with signal 9
17 Runtime error 388 ms 1048576 KB Execution killed with signal 9
18 Runtime error 372 ms 1048576 KB Execution killed with signal 9

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 399 ms 1048576 KB Execution killed with signal 9
2 Runtime error 359 ms 1048576 KB Execution killed with signal 9
3 Runtime error 375 ms 1048576 KB Execution killed with signal 9
4 Runtime error 357 ms 1048576 KB Execution killed with signal 9
5 Runtime error 365 ms 1048576 KB Execution killed with signal 9
6 Runtime error 359 ms 1048576 KB Execution killed with signal 9
7 Runtime error 371 ms 1048576 KB Execution killed with signal 9
8 Runtime error 381 ms 1048576 KB Execution killed with signal 9
9 Runtime error 369 ms 1048576 KB Execution killed with signal 9
10 Runtime error 377 ms 1048576 KB Execution killed with signal 9
11 Runtime error 362 ms 1048576 KB Execution killed with signal 9
12 Runtime error 393 ms 1048576 KB Execution killed with signal 9
13 Runtime error 381 ms 1048576 KB Execution killed with signal 9
14 Runtime error 359 ms 1048576 KB Execution killed with signal 9
15 Runtime error 363 ms 1048576 KB Execution killed with signal 9
16 Runtime error 357 ms 1048576 KB Execution killed with signal 9
17 Runtime error 344 ms 1048576 KB Execution killed with signal 9
18 Runtime error 332 ms 1048576 KB Execution killed with signal 9
19 Runtime error 332 ms 1048576 KB Execution killed with signal 9
20 Runtime error 346 ms 1048576 KB Execution killed with signal 9
21 Runtime error 372 ms 1048576 KB Execution killed with signal 9
22 Runtime error 392 ms 1048576 KB Execution killed with signal 9
23 Runtime error 361 ms 1048576 KB Execution killed with signal 9
24 Runtime error 370 ms 1048576 KB Execution killed with signal 9
25 Runtime error 372 ms 1048576 KB Execution killed with signal 9
26 Runtime error 362 ms 1048576 KB Execution killed with signal 9
27 Runtime error 373 ms 1048576 KB Execution killed with signal 9
28 Runtime error 376 ms 1048576 KB Execution killed with signal 9
29 Runtime error 384 ms 1048576 KB Execution killed with signal 9
30 Runtime error 330 ms 1048576 KB Execution killed with signal 9
31 Runtime error 377 ms 1048576 KB Execution killed with signal 9
32 Runtime error 365 ms 1048576 KB Execution killed with signal 9