// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair
template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
int dx[4] = { 0, 0, -1, +1};
int dy[4] = {-1, +1, 0, 0};
const int SQ = 700; // determines what is heavy and what is light
int main() {
cin.tie(0)->sync_with_stdio(0);
// Paint
int N, M; cin >> N >> M;
// auto P = [&](int x) {
// return "{ " + to_string(x / M) + " " + to_string(x % M) + " }";
// };
V<vi> A(N, vi(M)); for(int r = 0; r < N; r++) for(int c = 0; c < M; c++) {
cin >> A[r][c];
}
vi ID(N * M), C(N * M), H(N * M, 0); V<vi> E(N * M); V<set<int>> EH(N * M); V<set<pi>> L(N * M);
// L -> adj to the set (color, vertex)
vpi CMB;
for(int r = 0; r < N; r++) for(int c = 0; c < M; c++) {
ID[r * M + c] = r * M + c;
for(int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
E[r * M + c].pb(nr * M + nc); // add edge between adj. cells
if (A[r][c] == A[nr][nc]) CMB.pb(mp(r * M + c, nr * M + nc));
}
C[r * M + c] = A[r][c];
}
function<int(int)> get = [&](int u) {
return ID[u] == u ? u : ID[u] = get(ID[u]);
};
auto merge = [&](int u, int v) {
// cout << u / M << " " << u % M << " <= U => " << v / M << " " << v % M << endl;
u = get(u), v = get(v);
if (u == v) return;
if (sz(E[u]) < sz(E[v])) swap(u, v);
if (sz(EH[u]) < sz(EH[v])) EH[u].swap(EH[v]);
if (sz(L[u]) < sz(L[v])) L[u].swap(L[v]);
for(auto x : E[v]) {
x = get(x);
if (H[x]) { // is hvy
L[x].erase(mp(C[v], v));
L[x].insert(mp(C[u], u));
if (H[u]) {
EH[x].insert(u);
EH[u].insert(x);
}
}
E[u].pb(x);
}
for(auto& x : EH[v]) EH[u].insert(get(x));
for(auto& x : L[v]) L[u].insert(x);
ID[v] = u;
if (!H[u] && sz(E[u]) > SQ) {
H[u] = 1;
for(auto x : E[u]) {
int r = get(x);
if (r == u) continue;
L[u].insert(mp(C[r], r));
if (H[r]) { // is hvy => hvy together
EH[r].insert(u);
EH[u].insert(r);
}
}
}
};
for(auto& p : CMB) {
auto [u, v] = p;
merge(u, v);
}
// for(int r = 0; r < N; r++) {
// cout << "--------------------------------" << nl;
// for(int c = 0; c < M; c++) {
// int u = r * M + c; cout << P(get(u)) << " | ";
// }
// cout << nl;
// }
int Q; cin >> Q;
for(int i = 0; i < Q; i++) {
int r, c, s; cin >> r >> c >> s; --r, --c;
// if (i % 100 == 0) cout << i << endl;
int u = r * M + c; u = get(u);
// s stores the old color
swap(C[u], s);
vi cmb;
if (H[u]) { // if heavy: (~1900 iters)
// go through heavy nodes -> N / B
for(auto& v : EH[u]) {
int rx = get(v);
// cout << P(u) << " <= HH => " << P(rx) << nl;
if (rx != u && C[rx] == C[u]) cmb.pb(rx);
}
// go through light nodes -> log(N)
{
while(1) {
auto it = L[u].lower_bound(mp(C[u], -1));
if (it == end(L[u])) break;
auto [cv, v] = *it;
v = get(v);
if (cv == C[u]) {
if (C[v] == C[u]) cmb.pb(v);
L[u].erase(it);
} else break;
}
}
} else { // if light: (~1900 iters)
// go through all adjacent -> B * log(N)
for(auto& v : E[u]) {
int rx = get(v);
if (rx != u && C[rx] == C[u]) cmb.pb(rx);
if (H[rx]) { // is hvy
L[rx].erase(mp(s, u));
L[rx].insert(mp(C[u], u));
}
}
}
for(auto& x : cmb) merge(u, x);
}
// after updates find the adjacents with the same color
// two parts -> color and adjacent
// can store either color or adjacent
// how do you check whether adjacent with a color?
// with adjacent you have to find color efficiently
// if you store (color, vertex) pair in a set, then you can find the adjacents quickly
// you also have to update them
// SQRT Decomp? but its N * sqrt(N) * log(N)?
// Light -> B * log(N) + (N / B), heavy -> N / B + log(N)
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
int u = r * M + c; cout << C[get(u)] << " ";
}
cout << nl;
}
exit(0-0);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2004 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
1884 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
10128 KB |
Output is correct |
| 2 |
Incorrect |
103 ms |
21448 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
65 ms |
35924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
82 ms |
28636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
