QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372254 | #1943. Borders | ohiostatescarlet# | TL | 0ms | 0kb | C++17 | 2.3kb | 2024-03-31 07:51:38 | 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...