oj.uz

Submission #1094327

# Submission time Handle Problem Language Result Execution time Memory
1094327 2024-09-29T10:40:37 Z MattNattFeczan Tracks in the Snow (BOI13_tracks) C++14
73.75 / 100
 1326 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], c=1;
bool c1[N*N], c2[N*N];
vector<int>Graf[N*N];

void DFS1(int n, int v){
  c1[n] = c, idx[n] = v;
  for(auto& elm : Graf1[n]){
    if(!c1[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(!c1[i])
      DFS1(i, v++);
  }
  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(c2[now.first] == c)
      continue;
    c2[now.first] = c, d = max(d, now.second);
    for(auto& elm : Graf[now.first]){
      if(c2[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 330 ms 767520 KB Output is correct
2 Correct 290 ms 751692 KB Output is correct
3 Correct 290 ms 751952 KB Output is correct
4 Correct 315 ms 761940 KB Output is correct
5 Correct 319 ms 753492 KB Output is correct
6 Correct 326 ms 751816 KB Output is correct
7 Correct 320 ms 751896 KB Output is correct
8 Correct 352 ms 752208 KB Output is correct
9 Correct 307 ms 751956 KB Output is correct
10 Correct 316 ms 753784 KB Output is correct
11 Correct 316 ms 754512 KB Output is correct
12 Correct 329 ms 757332 KB Output is correct
13 Correct 313 ms 753392 KB Output is correct
14 Correct 312 ms 753420 KB Output is correct
15 Correct 360 ms 764120 KB Output is correct
16 Correct 344 ms 767420 KB Output is correct
17 Correct 348 ms 759168 KB Output is correct
18 Correct 347 ms 761828 KB Output is correct

Subtask #2
43.75 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 752980 KB Output is correct
2 Correct 439 ms 798800 KB Output is correct
3 Runtime error 949 ms 1048576 KB Execution killed with signal 9
4 Correct 574 ms 804692 KB Output is correct
5 Runtime error 761 ms 1048576 KB Execution killed with signal 9
6 Runtime error 792 ms 1048576 KB Execution killed with signal 9
7 Correct 304 ms 752720 KB Output is correct
8 Correct 309 ms 752980 KB Output is correct
9 Correct 328 ms 754048 KB Output is correct
10 Correct 321 ms 752656 KB Output is correct
11 Correct 308 ms 752664 KB Output is correct
12 Correct 324 ms 752724 KB Output is correct
13 Correct 441 ms 798860 KB Output is correct
14 Correct 397 ms 779444 KB Output is correct
15 Correct 387 ms 771748 KB Output is correct
16 Correct 397 ms 776276 KB Output is correct
17 Correct 648 ms 870740 KB Output is correct
18 Correct 684 ms 829224 KB Output is correct
19 Correct 549 ms 804508 KB Output is correct
20 Correct 527 ms 822096 KB Output is correct
21 Correct 781 ms 933588 KB Output is correct
22 Runtime error 1026 ms 1048576 KB Execution killed with signal 9
23 Correct 990 ms 984092 KB Output is correct
24 Correct 665 ms 948508 KB Output is correct
25 Runtime error 1326 ms 1048576 KB Execution killed with signal 9
26 Runtime error 818 ms 1048576 KB Execution killed with signal 9
27 Runtime error 842 ms 1048576 KB Execution killed with signal 9
28 Runtime error 827 ms 1048576 KB Execution killed with signal 9
29 Runtime error 829 ms 1048576 KB Execution killed with signal 9
30 Runtime error 781 ms 1048576 KB Execution killed with signal 9
31 Runtime error 822 ms 1048576 KB Execution killed with signal 9
32 Runtime error 778 ms 1048576 KB Execution killed with signal 9