QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372250 | #1943. Borders | ohiostatescarlet# | WA | 2ms | 5864kb | C++17 | 2.2kb | 2024-03-31 07:15:28 | 2024-03-31 07:15:29 |
Judging History
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';
}
Details
Tip: Click on the bar to expand more detailed information
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'