Submission #1094306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094306		MattNattFeczan	Tracks in the Snow (BOI13_tracks)	C++14	73.75 / 100	1153 ms	1048576 KiB

tracks

#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 / 30
• Subtask 2: 43.75 / 70