QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372254#1943. Bordersohiostatescarlet#TL 0ms0kbC++172.3kb2024-03-31 07:51:382024-03-31 07:51:38

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 07:51:38]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-03-31 07:51:38]
  • 提交

answer

#include"bits/stdc++.h"
using namespace std;
#define L long long
#ifdef LOCAL
#define dbg(x...) cerr << '[' << #x << " = " << (x) << ']' << endl;
#else
#define dbg(x...)
#endif
// g++ -std=c++17 -O2 -DLOCAL -o a a.cpp
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<int> dsu(n*m, -1);
  function<int(int)> find = [&](int x) {
    return (dsu[x]<0) ? x : (dsu[x] = find(dsu[x]));
  };
  auto join = [&](int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (dsu[x] > dsu[y]) swap(x,y);
    dsu[x] += dsu[y];
    dsu[y] = x;
  };
  auto idx = [&](int line, int pos) {
    return line + pos * n;
  };
  vector<string> grid(n);
  for (int i = 0; i < n; i++)
  {
    cin >> grid[i];
  }
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++) {
      if (j + 1 < m && grid[i][j] == grid[i][j+1]) join(idx(i,j),idx(i,j+1));
      if (i + 1 < n && grid[i][j] == grid[i+1][j]) join(idx(i,j),idx(i+1,j));
    }
  }
  vector<set<int>> edges(n*m);
  set<int> req;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++) {
      if (i == 0 || j == 0 || i == n-1 || j == m-1) {
        req.insert(find(idx(i,j)));
      }
      if (j + 1 < m && grid[i][j] != grid[i][j+1]) {
        edges[find(idx(i,j))].insert(find(idx(i,j+1)));
        edges[find(idx(i,j+1))].insert(find(idx(i,j)));
      }
      if (i + 1 < n && grid[i][j] != grid[i+1][j]) {
        edges[find(idx(i,j))].insert(find(idx(i+1,j)));
        edges[find(idx(i+1,j))].insert(find(idx(i,j)));
      }
    }
  }
  int res = req.size();
  for (int x : req) {
    for (int v : edges[x]) {
      edges[v].erase(x);
    }
    edges[x].clear();
  }
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
  for (int i = 0; i < n*m; i++) {
    if (edges[i].size()) {
      q.push({edges[i].size(), i});
    }
  }
  while (q.size()) {
    auto [d, x] = q.top(); q.pop();
    if (d == edges[x].size()) {
      for (int v1 : edges[x]) {
        res++;
        for (int v2 : edges[v1]) {
          if (v2 == d) continue;
          edges[v2].erase(v1);
          if (edges[v2].size()) {
            q.push({edges[v2].size(), v2});
          }
        }
        edges[v1].clear();
      }
    }
  }
  cout << res << '\n';
}

/*

3 3
010
101
010

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

100 100
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:


result: