oj.uz

Submission #1094311

# Submission time Handle Problem Language Result Execution time Memory
1094311 2024-09-29T10:31:14 Z MattNattFeczan Tracks in the Snow (BOI13_tracks) C++14
62.8125 / 100
 1051 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++;
  set<int>Sets[v];
  for(int i=0;i<n*m;i++){
    for(auto& elm : Graf1[i]){
      if(idx[elm.second] != idx[i] && !Sets[idx[i]].count(idx[elm.second]))
        Graf[idx[i]].push_back(idx[elm.second]), Sets[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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 773456 KB Output is correct
2 Correct 306 ms 752036 KB Output is correct
3 Correct 327 ms 752208 KB Output is correct
4 Correct 347 ms 762232 KB Output is correct
5 Correct 407 ms 757840 KB Output is correct
6 Correct 316 ms 752052 KB Output is correct
7 Correct 327 ms 752188 KB Output is correct
8 Correct 309 ms 752468 KB Output is correct
9 Correct 308 ms 752468 KB Output is correct
10 Correct 303 ms 756816 KB Output is correct
11 Correct 309 ms 754768 KB Output is correct
12 Correct 334 ms 759636 KB Output is correct
13 Correct 300 ms 757944 KB Output is correct
14 Correct 299 ms 757840 KB Output is correct
15 Correct 336 ms 773180 KB Output is correct
16 Correct 356 ms 773716 KB Output is correct
17 Correct 326 ms 771668 KB Output is correct
18 Correct 351 ms 762096 KB Output is correct

Subtask #2
32.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 755280 KB Output is correct
2 Correct 491 ms 874324 KB Output is correct
3 Runtime error 730 ms 1048576 KB Execution killed with signal 9
4 Correct 679 ms 1000564 KB Output is correct
5 Runtime error 611 ms 1048576 KB Execution killed with signal 9
6 Runtime error 790 ms 1048576 KB Execution killed with signal 9
7 Correct 278 ms 754772 KB Output is correct
8 Correct 314 ms 755248 KB Output is correct
9 Correct 282 ms 756560 KB Output is correct
10 Correct 320 ms 753868 KB Output is correct
11 Correct 307 ms 754768 KB Output is correct
12 Correct 306 ms 754892 KB Output is correct
13 Correct 504 ms 874340 KB Output is correct
14 Correct 422 ms 822864 KB Output is correct
15 Correct 456 ms 827732 KB Output is correct
16 Correct 418 ms 804764 KB Output is correct
17 Runtime error 673 ms 1048576 KB Execution killed with signal 9
18 Runtime error 675 ms 1048576 KB Execution killed with signal 9
19 Correct 658 ms 1000552 KB Output is correct
20 Correct 619 ms 997868 KB Output is correct
21 Runtime error 613 ms 1048576 KB Execution killed with signal 9
22 Runtime error 635 ms 1048576 KB Execution killed with signal 9
23 Runtime error 743 ms 1048576 KB Execution killed with signal 9
24 Runtime error 581 ms 1048576 KB Execution killed with signal 9
25 Runtime error 1051 ms 1048576 KB Execution killed with signal 9
26 Runtime error 753 ms 1048576 KB Execution killed with signal 9
27 Runtime error 734 ms 1048576 KB Execution killed with signal 9
28 Runtime error 774 ms 1048576 KB Execution killed with signal 9
29 Runtime error 762 ms 1048576 KB Execution killed with signal 9
30 Runtime error 811 ms 1048576 KB Execution killed with signal 9
31 Runtime error 820 ms 1048576 KB Execution killed with signal 9
32 Runtime error 744 ms 1048576 KB Execution killed with signal 9