Submission #605191

#	Time	Username	Problem	Language	Result	Execution time	Memory
605191		jackkkk	Tracks in the Snow (BOI13_tracks)	C++11	0 / 100	1491 ms	1048576 KiB

tracks

// Tracks in the Snow
// https://oj.uz/problem/view/BOI13_tracks

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <cassert>
using namespace std;


void quit() {
  cout.flush();
  exit(0);
}
char grid[4002][4002]; char gridcpy[4002][4002];
vector<unordered_set<int>> adj;
int id[4002][4002];
int curr_id = 1;
deque <pair<int, int>> dq;
pair<int, int> gto[4] = {{1,0},{0,1},{-1,0},{0,-1}};
void flood(int a, int b){
  id[a][b]=curr_id;
  char c = grid[a][b];
  grid[a][b]='.';
  dq.emplace_back(a, b);
  while(!dq.empty()){
    auto curr = dq.front();
    dq.pop_front();
    for(auto to : gto){
      int nxt1 = curr.first+to.first, nxt2 = curr.second+to.second;
      if(grid[nxt1][nxt2] == c){
        id[nxt1][nxt2]=curr_id;
        grid[nxt1][nxt2] = '.';
        dq.emplace_back(nxt1, nxt2);
      }
    }
  }
  curr_id++;
}

int main(void){
  //freopen("qwer.in", "r", stdin);
  //freopen("qwer.out", "w", stdout);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m; cin >> n >> m;
  for(int i = 0; i < 4002; i++){
    for(int j = 0; j < 4002; j++){
      grid[i][j]='.';
      gridcpy[i][j]='.';
    }
  }
  for(int i = 1; i <= n; i++){
    string s; cin >> s;
    for(int j = 1; j <= m; j++){
      grid[i][j]=s[j-1];
      gridcpy[i][j]=grid[i][j];
    }
  }
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(grid[i][j] != '.'){
        flood(i, j);
      }
    }
  }
  adj.resize(curr_id+10);
  for(int i = 1; i < n; i++){
    for(int j = 1; j < m; j++){
      if(gridcpy[i][j]!= '.' && gridcpy[i][j+1] != '.' && gridcpy[i][j] != gridcpy[i][j+1]){
        adj[id[i][j]].insert(id[i][j+1]);
        adj[id[i][j+1]].insert(id[i][j]);
      }
      if(gridcpy[i][j]!= '.' && gridcpy[i+1][j] != '.' && gridcpy[i][j] != gridcpy[i+1][j]){
        adj[id[i][j]].insert(id[i+1][j]);
        adj[id[i+1][j]].insert(id[i][j]);
      }
    }
  }
  quit();
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70