oj.uz

Submission #1094324

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

const int N = 4000;
string S[2];
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++){
    S[0] = S[1];
    cin>>S[1];
    for(int j=0;j<m;j++){
      if(S[1][j] == '.')
        continue;
      if(i != 0){
        if(S[0][j] == S[1][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[0][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[1][j-1] == S[1][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[1][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 358 ms 767824 KB Output is correct
2 Correct 293 ms 751700 KB Output is correct
3 Correct 307 ms 752008 KB Output is correct
4 Correct 311 ms 762196 KB Output is correct
5 Correct 307 ms 753416 KB Output is correct
6 Correct 294 ms 751700 KB Output is correct
7 Correct 298 ms 751956 KB Output is correct
8 Correct 294 ms 752228 KB Output is correct
9 Correct 294 ms 751956 KB Output is correct
10 Correct 295 ms 754076 KB Output is correct
11 Correct 310 ms 754516 KB Output is correct
12 Correct 308 ms 757524 KB Output is correct
13 Correct 290 ms 753548 KB Output is correct
14 Correct 305 ms 753468 KB Output is correct
15 Correct 327 ms 764496 KB Output is correct
16 Correct 343 ms 767948 KB Output is correct
17 Correct 322 ms 759636 KB Output is correct
18 Correct 337 ms 762200 KB Output is correct

Subtask #2
43.75 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 753044 KB Output is correct
2 Correct 431 ms 801364 KB Output is correct
3 Runtime error 781 ms 1048576 KB Execution killed with signal 9
4 Correct 504 ms 810068 KB Output is correct
5 Runtime error 694 ms 1048576 KB Execution killed with signal 9
6 Runtime error 764 ms 1048576 KB Execution killed with signal 9
7 Correct 303 ms 752976 KB Output is correct
8 Correct 301 ms 752980 KB Output is correct
9 Correct 284 ms 754004 KB Output is correct
10 Correct 285 ms 752580 KB Output is correct
11 Correct 286 ms 752720 KB Output is correct
12 Correct 264 ms 752728 KB Output is correct
13 Correct 390 ms 801152 KB Output is correct
14 Correct 352 ms 780688 KB Output is correct
15 Correct 389 ms 773200 KB Output is correct
16 Correct 382 ms 777400 KB Output is correct
17 Correct 623 ms 877140 KB Output is correct
18 Correct 638 ms 835284 KB Output is correct
19 Correct 522 ms 810232 KB Output is correct
20 Correct 451 ms 827224 KB Output is correct
21 Correct 693 ms 948308 KB Output is correct
22 Runtime error 686 ms 1048576 KB Execution killed with signal 9
23 Correct 971 ms 997224 KB Output is correct
24 Correct 742 ms 964188 KB Output is correct
25 Runtime error 1051 ms 1048576 KB Execution killed with signal 9
26 Runtime error 816 ms 1048576 KB Execution killed with signal 9
27 Runtime error 866 ms 1048576 KB Execution killed with signal 9
28 Runtime error 792 ms 1048576 KB Execution killed with signal 9
29 Runtime error 771 ms 1048576 KB Execution killed with signal 9
30 Runtime error 775 ms 1048576 KB Execution killed with signal 9
31 Runtime error 789 ms 1048576 KB Execution killed with signal 9
32 Runtime error 763 ms 1048576 KB Execution killed with signal 9