oj.uz

Submission #1094322

# Submission time Handle Problem Language Result Execution time Memory
1094322 2024-09-29T10:36:33 Z MattNattFeczan Tracks in the Snow (BOI13_tracks) C++14
65 / 100
 995 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++;
  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++){
    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 354 ms 773024 KB Output is correct
2 Correct 291 ms 751952 KB Output is correct
3 Correct 337 ms 752324 KB Output is correct
4 Correct 330 ms 761940 KB Output is correct
5 Correct 306 ms 757588 KB Output is correct
6 Correct 303 ms 751788 KB Output is correct
7 Correct 300 ms 751912 KB Output is correct
8 Correct 299 ms 752212 KB Output is correct
9 Correct 293 ms 752468 KB Output is correct
10 Correct 300 ms 756820 KB Output is correct
11 Correct 306 ms 754768 KB Output is correct
12 Correct 314 ms 759436 KB Output is correct
13 Correct 306 ms 757540 KB Output is correct
14 Correct 305 ms 757588 KB Output is correct
15 Correct 364 ms 772948 KB Output is correct
16 Correct 358 ms 772944 KB Output is correct
17 Correct 330 ms 771412 KB Output is correct
18 Correct 320 ms 761940 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 755160 KB Output is correct
2 Correct 484 ms 872532 KB Output is correct
3 Runtime error 724 ms 1048576 KB Execution killed with signal 9
4 Correct 626 ms 996604 KB Output is correct
5 Runtime error 601 ms 1048576 KB Execution killed with signal 9
6 Runtime error 745 ms 1048576 KB Execution killed with signal 9
7 Correct 303 ms 754832 KB Output is correct
8 Correct 302 ms 755040 KB Output is correct
9 Correct 301 ms 756304 KB Output is correct
10 Correct 304 ms 754000 KB Output is correct
11 Correct 304 ms 754632 KB Output is correct
12 Correct 306 ms 754884 KB Output is correct
13 Correct 473 ms 872528 KB Output is correct
14 Correct 414 ms 821708 KB Output is correct
15 Correct 428 ms 826448 KB Output is correct
16 Correct 386 ms 803720 KB Output is correct
17 Runtime error 630 ms 1048576 KB Execution killed with signal 9
18 Correct 907 ms 1048408 KB Output is correct
19 Correct 671 ms 996592 KB Output is correct
20 Correct 591 ms 994132 KB Output is correct
21 Runtime error 589 ms 1048576 KB Execution killed with signal 9
22 Runtime error 588 ms 1048576 KB Execution killed with signal 9
23 Runtime error 657 ms 1048576 KB Execution killed with signal 9
24 Runtime error 535 ms 1048576 KB Execution killed with signal 9
25 Runtime error 995 ms 1048576 KB Execution killed with signal 9
26 Runtime error 718 ms 1048576 KB Execution killed with signal 9
27 Runtime error 735 ms 1048576 KB Execution killed with signal 9
28 Runtime error 748 ms 1048576 KB Execution killed with signal 9
29 Runtime error 754 ms 1048576 KB Execution killed with signal 9
30 Runtime error 763 ms 1048576 KB Execution killed with signal 9
31 Runtime error 836 ms 1048576 KB Execution killed with signal 9
32 Runtime error 788 ms 1048576 KB Execution killed with signal 9