제출 #1094308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094308		MattNattFeczan	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	399 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;
set<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]].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: 0 / 30
• Subtask 2: 0 / 70