QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372250#1943. Bordersohiostatescarlet#WA 2ms5864kbC++172.2kb2024-03-31 07:15:282024-03-31 07:15:29

Judging History

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

  • [2024-03-31 07:15:29]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5864kb
  • [2024-03-31 07:15:28]
  • 提交

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>>, less<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()) {
      res++;
      for (int v : edges[x]) {
        edges[v].erase(x);
        if (edges[v].size()) {
          q.push({edges[v].size(), v});
        }
      }
      edges[x].clear();
    }
  }
  cout << res << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5864kb

input:

100 100
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

5198

result:

ok single line: '5198'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

5 6
001011
010101
100110
010101
001011

output:

12

result:

ok single line: '12'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3828kb

input:

6 10
1110100000
1101011110
1010011010
1101010110
1010011110
1101100000

output:

12

result:

wrong answer 1st lines differ - expected: '11', found: '12'