oj.uz

Submission #1094306

# Submission time Handle Problem Language Result Execution time Memory
1094306 2024-09-29T10:23:29 Z MattNattFeczan Tracks in the Snow (BOI13_tracks) C++14
73.75 / 100
 1153 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]);
    }
  }
  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(){
  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 357 ms 768596 KB Output is correct
2 Correct 295 ms 751952 KB Output is correct
3 Correct 311 ms 751872 KB Output is correct
4 Correct 331 ms 762708 KB Output is correct
5 Correct 317 ms 753716 KB Output is correct
6 Correct 293 ms 751952 KB Output is correct
7 Correct 297 ms 751992 KB Output is correct
8 Correct 303 ms 752192 KB Output is correct
9 Correct 300 ms 752064 KB Output is correct
10 Correct 283 ms 754100 KB Output is correct
11 Correct 276 ms 754804 KB Output is correct
12 Correct 290 ms 757840 KB Output is correct
13 Correct 277 ms 753744 KB Output is correct
14 Correct 275 ms 753744 KB Output is correct
15 Correct 323 ms 765196 KB Output is correct
16 Correct 351 ms 768576 KB Output is correct
17 Correct 344 ms 760336 KB Output is correct
18 Correct 321 ms 762708 KB Output is correct

Subtask #2
43.75 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 753068 KB Output is correct
2 Correct 444 ms 805240 KB Output is correct
3 Runtime error 898 ms 1048576 KB Execution killed with signal 9
4 Correct 564 ms 820996 KB Output is correct
5 Runtime error 822 ms 1048576 KB Execution killed with signal 9
6 Runtime error 887 ms 1048576 KB Execution killed with signal 9
7 Correct 319 ms 752980 KB Output is correct
8 Correct 307 ms 753060 KB Output is correct
9 Correct 297 ms 754260 KB Output is correct
10 Correct 305 ms 752908 KB Output is correct
11 Correct 303 ms 752720 KB Output is correct
12 Correct 312 ms 752720 KB Output is correct
13 Correct 460 ms 805204 KB Output is correct
14 Correct 402 ms 783208 KB Output is correct
15 Correct 389 ms 776212 KB Output is correct
16 Correct 391 ms 778836 KB Output is correct
17 Correct 724 ms 888768 KB Output is correct
18 Correct 722 ms 846724 KB Output is correct
19 Correct 568 ms 821076 KB Output is correct
20 Correct 518 ms 837528 KB Output is correct
21 Correct 842 ms 969520 KB Output is correct
22 Runtime error 835 ms 1048576 KB Execution killed with signal 9
23 Correct 1032 ms 1014352 KB Output is correct
24 Correct 822 ms 984972 KB Output is correct
25 Runtime error 1153 ms 1048576 KB Execution killed with signal 9
26 Runtime error 814 ms 1048576 KB Execution killed with signal 9
27 Runtime error 789 ms 1048576 KB Execution killed with signal 9
28 Runtime error 900 ms 1048576 KB Execution killed with signal 9
29 Runtime error 850 ms 1048576 KB Execution killed with signal 9
30 Runtime error 830 ms 1048576 KB Execution killed with signal 9
31 Runtime error 809 ms 1048576 KB Execution killed with signal 9
32 Runtime error 785 ms 1048576 KB Execution killed with signal 9